|
Главная -> Справочник по алгоритмам 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 [21] 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 на О считается некорректной операцией. Большие погрешности возникают, если д,(*-)0, но является малым числом. Для повышения точности вычисления определителя и исключения останова ЭВМ в ходе вычислений применяются варианты метода Гаусса с выбором главного элемента по столбцу, строке или по всей матрице. В последнем случае перед преобразованиями в матрице А (3.5) выбирают наибольший по модулю (главный) элемент, допустим а,;. Далее переставляют первую строку матрицы с / й строкой (это и есть выбор главного элемента по строке), а первый столбец переставляют с /-м (выбор главного элемента по столбцу). При каждой такой перестановке знак определителя меняется, поэтому результат нужно умножить на (-1)", где Р - число перестановок. Программа 3.53. Пример. 3 4 4 7 = -20. Отметим, что вычисление этого определителя по программе 3.52 ведет к останову ЭВМ с индикацией ошибки (некорректная математическая операция). Обратной матрицей называется матрица Л~, произведение которой на заданную матрицу А дает единичную матрицу. Обращение матрицы А заключается в нахождении обратной матрицы Л". Для обращения матрицы Л используют следующие основные соотношения: л-л- =
Перемножая матрицы А и А получим п систем уравнений с неизвестными: OllJCll +012X21+ ...-fOin, = 1, 02 ixi I + 02221 + .. + 02„л:„ I = о, a„ix\ 1 + a„2X2i + - -. + a„„x„i =0. OllX2 + Ol2X22+...+O„X„2 = 0, O2IX12 + O22X22 + .- .+ 02„X„2=l, 0„ 1X12 +0„2X2J + . -. + 0„„X„2 = 0. o,iXi„+ai2X2„ + ...+oi„x„„ = 0, O21X„ + 022X2„ + ... -f 02„X„„ = 0, o„ ix I „+a„2X2„ +,.. + o„„x„„ = 1. («) Решение этих уравнений определяет значения всех элементов матрицы Ллу. Оио выполняется по методам, описанным в § 4.1. Для простых матриц обращение выполняется по программам, реализующим готовые «рецепты» процедуры обращения. Программа 3.54. IS PRIHTOEPAUJEHUE МАТРИЦЫ 2*2 2В INPUT-ВВЕДИТЕ Й1ЬЙ12 А/В 25 INPUTВВЕДИТЕ h21..h22 CjD 30 LETE=C*B: LETF=A5 LETE=ri«F-E! LETA=ri.--E 40 1 ЕТГ!=Р>Е: LETC=-C-E: LETB=-B-E 50 PRINT •ОБРАЩЕННАЯ МАТРИЦА 60 PRINT Й.Г В SPRINT С-В г ENB Пример. 7 8 4 5 л- = 1,66666667 - 2,666666667 -1,333333333 2,333333333 Программа 3.55. Пример. 4 8 0 8 8 8 2 О 1 л- = 0,083333 - 0,083333 0.66666 0,083333 0,041666 -0,33333 - 0,16666 0,16666 - 0,33333 (указаны 5 значащих цифр результата). Программа 3.56. Проверить эту программу можно по примеру, приведенному к программе 3.55. Сложение и вычитание для двух матриц Л и В с одинаковой размерностью тХп производится по формуле Cij=aij±b,j, где г = 1, 2, m и / = 1, 2, п. Здесь с,7 - элементы результирующей матрицы С. Программа 3.57. 05 PRINT-СП0Н1ЕНИЕ МАТРИЦ 10 INPUTВВЕДИТЕ МгН МтН 15 BIM Й.;МтН)/Б<М..Н)гС<М/Н) 20 FOR 1=1 ТО MiFOR J=l ТО N 30 PRINT!2,0!ВВЕДИТЕ AIrJ 40 INPUT H<I..J):NEXT J:NEXT I 50 FOR 1=1 TO MS FOR .J=l TO N 60 PR I NTВВЕДИТЕ BI.-J 65 INPUT BajJ> ?0 LETC<bJ)=A<bJ>+Ba,J> 88 NEXT JSHEXT ПЕНИ
Умножение матриц A с размерностью mXn и В с размерностью пХ/ выполняется по формуле SMt I (Oftfc.v). 1 = 1 где /=1, 2, ..., / и k=\, 2, .... m. Получаемая матрица С имеет размерность тХ- 10 PRIHT-ОБРАЩЕНИЕ МАТРИЦЫ ЗжЗЛИМ А<3,3> 15 ХНРиТВВЕДИТЕ AlbA12.A13 А< 1/1ЪАСЬ£5Atl..3> 2й ГНРиТВВЕДИТЕ A2bA2£A£3 А;£/1Ь А;2/2)т А<2.-3> £5 ХНРиТВВЕДИТЕ А31/А3£/А33 АСЗ.-1ЬАСЗ.2:)тАСЗтЗ) .30 FOR. К,=1 ТО 3 35 LETA=A*;£ 1 УУйС!. 1 >:LETB=-A 40 letc=A<2£)-A*A<b2)!LETri=A«L2..3)-A-*Aa/3> 50 LET А=А < Зг 1 >А а И :>: LET А <. 2f 3 )=-А 60 ЬЕТАС2т1>=А<3/2:5-АжА<12) ?0 LET А 2r 2 ) =А < 3.- 3 ) -А* А < 1 г 3 ) 88 LETA;3y 1 )=А; If2)-A< Ь 1) 90 LETA«l3/2>=ACb3)AaT 15 180 LETA<:3j3)=l-Aa/l)!LETA<bl)=c lie LETA<l7 2)=ri.LETAa/3>=B:NEXT К, 120 PRINTОБРАЩЕННАЯ МАТРИЦА 130 .PRINT А<Ы)тА<12Х.Аа7 3) 140 PRINT AC2rl)..A*L2..2)fAi;2/3) 158 PRINT A<3.. 1)..А<Зг2)/А;ЗгЗ>гЕНГ! Программа 3-56. 05 PRINTОБРАЩЕНИЕ МАТРИЦ МЕТОДОМ ГАУССА 10 PRINTc ВЫБОРОМ ГЛАВНОГО ЭЛЕМЕНТА 15 1НриТЗАДАйТЕ N=N!liIM A<NtN)j-P<N)N) 20 bim b«lN))C<:n.-n)).g<n),x<n) 25 for 1=1 TO nsfor J=l TO N 30 PRINT12.0!ВВЕДИТЕ ЙIrJ=s INPUT ACbJ) 35 LETPCbJ>=A<bJ)sNEXT JsNEXT I 40 FOR J2=l TO nsfor 1=1 TO N 50 LETB<I)=@sNEXT I 60 LETB<J2)=1 70 FOR J3=l TO NSFOR J4=l TO N 80 LETA<J3/J4>=P<J3fJ4)!NEXT J4SNEXT J3 85 GOSUB 100!FOR 1=1 TO N 90 PRINT!2.0XI.-J2=!F1.9!Xa) 95 NEXT I!NEXT J2SST0P 180 LETNl=N-ls FOR K=l TO N1 110 IF ABS<A<KrK))>8 GOTO 280 120 LETKl=K+lsFOR M=K1 TON 130 IF ABS<A<M.»K,>>>0 goto 150 140 GOTO 165 150 FOR L=l TO N!LETU=A<K/l)sLETA<KrL)=A<MTL) 160 LETA С Mr L > =U!NEXT L s NEXT M 170 LETU=B < К)s LETB < К)=B < M)!LETB < M)=U 200 LET9 < К)=B <К)A< К)s LETK1=K+1 210 FOR I=K1 TO N!LETBa>=B<I>-A<bK)*6«LK) 220 FOR J1=K TO N!LETJ=N-Jl+K!LETC<Kf J)=A«LKrJ).A<K/K> 225 LETA<Ij J)=A<Ir J)-A<bK)»iC<K,r J) 230 NEXT JlsNEXT Is NEXT К 240 LETM=Ns LETX< M)=B<M)A <M > 250 LETM=M-1:L.ETS=0SFOR L=M TO N1 260 LETS=S+c<MrL+l)*X<L+l)!NEXT L 270 letx<:m>=g<:m)-ssif m>i goto 250 280 return:enb . . Программа 3.58. • • 10 PRINTУМНОЖЕНИЕ МАТРИЦ МжН И N-*l 20 INPUTВВЕДИТЕ MfNrLMrNrL 30 bim A<MrN)/B<NrL)rC«LN/L) 40 FOR 1=1 TO M:F0R J=1 TO N 50 PRINT!2.8!ВВЕДИТЕ AIfJ:INPUT A<IrJ> 68 NEXT JSNEXT I 70 FOR 1=1 TO NSFOR J=l TO L 80 PRINTВВЕДИТЕ ВI, Js INPUT B<I..J> 90 NEXT JSNEXT I 108 FOR K=l TO MsFOR .J=l TO LsLETS=8 110 FOR 1=1 TO NsLETS=S+A<k>I)i«B<b JJsNEXT I 120 LETC<KrJ>=SsNEXT JsNEXT К 138 PRINTРЕЗУЛЬТАТ 140 FOR K,=l TO MSFOR J=l TO L 150 PRINT!2.0!cK:fJ=!F1.9!c<K,, J) 160 NEXT JSNEXT KSEND Программа 3.58. Прим ер. Для т-1 2 3 = 4, п = 5, / = 3 j 2 3 4 5 6 7 8 9! 2 3 4 5 6 7 8 9 ! 2 15 30 45 31 62 93 20 40 81 27 54 »t Умножение Чги г,..... 1 2 3 I 2 3 I 2 3 I 2 3. матрацы на вектор R== г,,,! выполняется по формуле где г=1, 2, .... т. В результате получаем вектор £У.={ьь U2, Vm\- Скалярное произведеЛие векторов А = ={аи 02, oj и В={Ьи bi.....b„] есть число 1 = 1 где /= L 2, п. Ввиду простоты составления программ для двук последних операций они не приводятся. § 3.6. Вычисление и комбинаторика факториалок Факториал Цри целом п1 ,n! = n-(n-l)-(n-2)-...- 2-1 (3.6) с особым случаем О! = I у ряда ПЭВМ может вычисляться микропрограммно (найример, с помощью оператора ! у ПЭВМ FX-702P>. Если такой возможности нет, вычисление факториала проводится по формуле (3.6). Программа 3.S9. 05 РР1ЫТВЫЧИСЛЕНИЕ ФйКТОРИйЛй 10 I№UT ВВЕДИТЕ ЧИСЛО ЧИСЕЛ N=N 20 LET 1=0! LET Р=1 38 LET 1=1+1LET Р=Р*.1 40 IF KN THEN 30 50 PRINT ФЙКТОРИЙЛ N!=P 70 90T0 10! END Пример 5!= 120, 1О! = 36288О0. При к -70 значения пГ выходят за rtpe-делы разрядности болвшииства ПЭВМ (п!> Ю). Для приближенного вычисления -фак-торнала больших чисел п гГрмейяется формула Стирлинга [iO, 36]. Функция пГ! вычисляется по формуле п!1 = й(п -2)-...-1 при нечетном п, п(п -2)-...-2 при четном п. Программа 3.60. Пример. 7!! = 105, 8!! = 384. Число перестановок. Р„ = п!, а Число размещений из п элемеитов по -т /4„" = ftV(n -т).. Число сочетаний из й элементов по m С™ = п!/((п-т)!тГ),-причем п>1 и 1<т<п. Программа 3.61. Пример. Для m = 5 и /г = IО rfo-лучим Pi о = 3628800, Л?о=30240 и С?о = 252. Подобным способом .можно вычислять и другие функции, содержащие члены с факториалами. Программа 3.60. 85 PRГНТВЫЧИСЛЕНИЕ ФУНКЦИИ N!! 18 INPUTВВЕДИТЕ ЧИСЛО N=N!LETft=N2!LETB=l 15 FOR 1=1 ТО 10 20 IF A-INT<A>=0 THEN 68 30 FOR 1=1 TO N STEP 2 48 ЕЕТВ=Вж1!NEXT I 50 GOTO 80 60 FOR J=2 TO N STEP £ 70 LETB=B*J!NbXT J 80 PRINTЗНАЧЕНИЕ N!!=B 98 GOTO 10!END Программа 3.61. 18 PRINTРАСЧЕТ Ч1СЛА ПЕРЕСТАНОВОК,- РАЗМЕЩЕНИЙ 28 PRINTИ СОЧЕТЙНИй ИЗ N ЭЛЕМЕНТОВ ПО М 38 INPUTВВЕДИТЕ ЦЕЛЫЕ ЧИСЛЙ Н/ М NrM 40 LETX=N!GOBUB 100!LETP=R 50 LETX=N-M! GOSUB 188! ЕЕТЙ=Р.-Р 60 LETX=M!GOSUB 100sLETC=ftR 76 PRINTЧИСЛО ПЕРЕСТАНОВОК PN=P 80 РРШТЧИСЛО РАЗМЕЩЕНИЙ A M.tN=A 90 PRINTЧИСЛО СОЧЕТАНИЙ С MrN=C!STCP 100 LETR=1EF0R I=X TO 1 STEP -1 110 LETR=R*l!NEXT isRETURNsEND 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 [21] 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 0.0233 |
|