Главная » Basic » МЕТОД ИСКЛЮЧЕНИЯ ГАУССА

0

Приведем набросок этого метода, который будет воплощен в виде  программы для ЭВМ: (а) Выбрать наибольший элемент в первом  столбце матрицы А.

(б)  Поменять местами первое уравнение (строку) с уравнением (строкой), содержащим выбранный элемент. При перестановке двух строк меняются местами и соответствующие элементы правой части b;    так  как порядок записи уравнений произволен, то при такой перестановке решение не изменяется.   Эта   операция  называется  выбором  ведущего  элемента  со   столбцами.  Если   наряду  с перестановкой строк допускается и перестановка столбцов, то можно осуществлять выбор главного элемента, однако при таких перестановках трудно регистрировать порядок следования переменных. (в)    Вычесть из всех низлежащих уравнений  такое кратное первого  уравнения, чтобы в  первом  столбце всюду, кроме первой строки, образовались нули. При этом  соответствующие  множители будут равны 21/a11), (a31/a11), (a41/a11)и т.  д. Проведенная в  (б)  перестановка минимизирует эти величины, что помогает уменьшить ошибки арифметических действий.

(г)   Повторить все действия, начиная с (а), используя второе уравнение и второй столбец вместо первого. Продолжать эти  действия для  следующих уравнений и  столбцов до  тех  пор,  пока  все

элементы  матрицы  А,  находящиеся ниже  главной  диагонали,  не  станут  нулями.  Тогда  система

уравнений примет вид

Ux=b’,

где U — верхняя треугольная матрица, т. е.

Такая система просто решается методом обратной подстановки. Последнее уравнение имеет вид

a’NNxN= b’N,

откуда следует, что xN=b’N a’NNМетод обратной подстановки выполняется следующим образом: (а) Вычислить из последнего уравнения xN.

(б)  Использовать полученное значение для решения предпоследнего уравнения, в котором отличны от нуля только коэффициенты При xN и xN-1.

(в) Использовать полученные значения xN и xN-1 для решения предыдущего уравнения относительно xN_2. Продолжать этот процесс для всех оставшихся уравнений, продвигаясь  обратно к первому уравнению. При его достижении система уравнений решена и получены решения х1 ,…, xN.

Так как каждое уравнение (строка) не зависит от остальных, то его можно умножить или поделить на произвольное (ненулевое) число, не изменив решения системы. Поэтому прямое сравнение значений коэффициентов в   столбцах  матрицы  А  при  поиске  ведущего элемента  не  является  наилучшим способом его выбора. Другой способ состоит в  сопоставлении значений этих  коэффициентов со значениями других коэффициентов в одном уравнении, сравнивая между собой вместо аij величины

Вычисления таких коэффициентов производятся подпрограммой в строке 990, а их сравнения и при необходимости перестановка уравнений подпрограммой в  строке 750. Попробуйте изменить  эту подпрограмму так, чтобы выбор осуществлялся по непреобразованным значениям; попробуйте также удалить оператор GOSUB в  строке 210. Тем самым выбор ведущего элемента будет  устранен и можно будет оценить влияние выбора. Эффект особенно заметен для матриц,  размеры которых превышают 10*10.

Дополнительные массивы С(,) и D( ) используются для сохранения исходных значений А(,) и В( ) в целях вычисления невязки (b-Aх). Отсутствие этих массивов не повлияет на решение системы,  но благодаря их наличию можно получить очень важные сведения о точности решения. Информация о значениях потенциальных ведущих элементов и о перестановке уравнений также очень полезна для понимания поведения решаемой системы.

Ниже приводится программа GAUSS:

10 REM ПРОГРАММА GAUSS С ВЫБОРОМ ГЛАВНОГО ЭЛЕМЕНТА

15 REM ПО СТОЛБЦАМ

20 DIM A(6,6),В(6),Х(6),С(6,6),D(6)

30 PRINT "РЕШЕНИЕ СИСТЕМЫ УРАВНЕНИЙ АХ=В"

40 INPUT "ЧИСЛО УРАВНЕНИЙ";N

50 PRINT "ВВЕДИТЕ МАТРИЦУ А (СТРОКА ЗА СТРОКОЙ)"

60 FOR I=1 TO N

70   FOR J=l TO N

80     INPUT A(I,J),

90     C(I,J)=A(I.J) 100   NEXT J 110 NEXT I

120 PRINT "ВВЕДИТЕ ВЕКТОР В"

130 FOR I=1 ТО N

140   INPUT B(I),

150   D(I)=B(I)

160 NEXT I

170 REM—–РЕШЕНИЕ СИСТЕМЫ—–

180 М=0

190 N1=N-1

200 FOR I=1 ТО N1

210   GOSUB 750

220   I1=I+1

230   FOR J=I1 TO N

240     P=A(J,I)/A(I,I)

250           PRINT "КОЭФФИЦИЕНТ ДЛЯ СТРОКИ" ;J; "СТОЛБЦА" ; I "РАВЕН" ;Р

260           FOR K=I1 TO N

270               A<J,K)=A<J,K)-P*ACI,K) ,

280           NEXT К

290           A(J,I)=0

300           B(J)=BJ)-P*B(I)

310       NEXT J

320  NEXT I

330 REM—–ОБРАТНАЯ ПОДСТАНОВКА—–

340 X(N)=B<N>/A(N,N)

350 I=N

360   I=I-1

370   I1=I+1

380   S=0

390   FOR J=I1 TO N

400     S=S+A<I,J)*X(J)

410   NEXT J

420   X(I)=(B(I)-S)/A(I,I)

430 IF I>1 THEN 360

440 REM ++++ПЕЧАТЬ РЕЗУЛЬТАТОВ++++

450 PRINT

460 PRINT "МАТРИЦА ПОСЛЕ ИСКЛЮЧЕНИЯ"

470 PRINT

480 FOR I=1 TO N

490   FOR J=l TO N

500     PRINT TAB(12*(J-l));A(I,J);

510   NEXT J

520   PRINT

530 NEXT I

540 PRINT

550 PRINT "ЧИСЛО ПЕРЕСТАНОВОК СТРОК =";М

560 PRINT

570 PRINT "РЕШЕНИЕ       НЕВЯЗКА"

580 PRINT "X                              <В-АХ)"

590 FOR 1=1 ТО N

600   S=0

610   FOR J=l TO N

620     S=S+C(I,J)*X(J)

630   NEXT J

640   PRINT X(I) ;TAB(16) ;D(I)-S

650 NEXT I

660 STOP

740 REM

750 REM ПОДПРОГРАММА ПЕРЕСТАНОВКИ СТРОК

760 REM ИЩЕТ НАИЛУЧШИЙ РАЗРЕШАЮЩИЙ ЭЛЕМЕНТ В СТОЛБЦЕ I

770 IF I=N THEN RETURN

780 L=0

790 FOR K=I TO N

800   GOSUB 990

810   PRINT "СТРОКА" ;К; "КОЭФФИЦИЕНТ" ;L1

820   IF L>=L1 THEN 850

830     I2=K

840     L=L1

850 NEXT К

860 IF I2=I THEN RETURN

870 M=M+1

880 REM ПЕРЕСТАНОВКА СТРОК I И I2

890 PRINT "ПЕРЕСТАНОВКА СТРОК" ; I 2 ; "И" ; I

900 FOR K=I TO N

910   S=A<I,K)

920   A(I,K)=A(I2.K)

930   A(I2,K)=S

940 NEXT К

950 S=B(I)

960 B(I)=B(I2)

970 B(I2)=S

980 RETURN

990 REM ПОДПРОГРАММА ОПРЕДЕЛЕНИЯ "ВЕСА" КОЭФФИЦИЕНТА В

995 REM СТРОКЕ К

1000 S=0

1010 FOR K1=I TO N

1020   S=S+A(K,K1)*A(K,K1)

1030 NEXT Kl

1040 L1=ABS(A(K,I)/SQR(S))

1050 RETURN

1060 END RUN

РЕШЕНИЕ СИСТЕМЫ УРАВНЕНИЙ АХ=В ЧИСЛО УРАВНЕНИЙ?3.

ВВЕДИТЕ МАТРИЦУ А (СТРОКА ЗА СТРОКОЙ)

?2.4.3

? 1.1.2

?3.5.2

ВВЕДИТЕ ВЕКТОР В

?0.2.1

СТРОКА 1 КОЭФФИЦИЕНТ .371391

СТРОКА 2 КОЭФФИЦИЕНТ .408248

СТРОКА 3 КОЭФФИЦИЕНТ .486664

ПЕРЕСТАНОВКА СТРОК 3 И 1

КОЭФФИЦИЕНТ ДЛЯ СТРОКИ 2 СТОЛБЦА 1 РАВЕН .333333

КОЭФФИЦИЕНТ ДЛЯ СТРОКИ 3 СТОЛБЦА 1 РАВЕН .666667

СТРОКА 2 КОЭФФИЦИЕНТ .447214

СТРОКА 3 КОЭФФИЦИЕНТ .371391

КОЭФФИЦИЕНТ ДЛЯ СТРОКИ 3 СТОЛБЦА 2 РАВЕН-1

МАТРИЦА ПОСЛЕ ИСКЛЮЧЕНИЯ

3

5

2

0

-.666667

1.33333

0

0

3

ЧИСЛО ПЕРЕСТАНОВОК СТРОК = 1

РЕШЕНИЕ        НЕВЯЗКА X                              (В-АХ) 3.16667                        0

-1.83333                      0

.333333                 4.36557Е-11

END AT  LINE  660

Источник: Уолш Б.    Программирование на Бейсике: Пер. с англ. М.: Радио и связь, 1988. 336 с: ил.

По теме:

  • Комментарии