МЕТОД виключення Гауса

Наведемо начерк цього методу, який буде втілено у вигляді програми для ЕОМ: (а) Вибрати найбільший елемент в першому стовпці матриці А

(Б) Поміняти місцями перше рівняння (рядок) з рівнянням (рядком), що містить обраний елемент При перестановці двох рядків міняються місцями і відповідні елементи правій частині b    так як порядок запису рівнянь довільний, то при такій перестановці рішення не змінюється Ця операція називається вибором ведучого елемента зі стовпцями Якщо поряд з перестановкою рядків допускається і перестановка стовпців, то можна здійснювати вибір головного елемента, однак при таких перестановках важко реєструвати порядок проходження змінних (В) Відняти з усіх низлежащих рівнянь таке кратне першого рівняння, щоб у першому стовпчику всюди, крім першого рядка, утворилися нулі При цьому відповідні множники будуть рівні 21/a11), (A31/a11), (a41/a11) і т д Проведена в (б) перестановка мінімізує ці величини, що допомагає зменшити помилки арифметичних дій

(Г) Повторити всі дії, починаючи з (а), використовуючи друге рівняння і другий стовпець замість першого Продовжувати ці дії для наступних рівнянь і стовпців до тих пір, поки всі

елементи матриці А, що знаходяться нижче головної діагоналі, не стануть нулями Тоді система

рівнянь прийме вигляд

Ux=b,

де U – Верхня трикутна матриця, тобто

Така система просто вирішується методом зворотної підстановки Останнє рівняння має вигляд

aNNxN= bN,

звідки випливає, що xN=bN aNNМетод зворотного підстановки виконується таким чином: (а) Обчислити з останнього рівняння 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(IJ) 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&ltJ,K)=A&ltJ,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&ltN&gt/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&ltI,J)*X(J)

410   NEXT J

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

430 IF I&gt1 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&gt=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&ltI,K)

920   A(I,K)=A(I2K)

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

Введіть матрицю А (рядок за рядком)

?243

? 112

?352

ВВЕДІТЬ ВЕКТОР У

?021

РЯДОК 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

133333

0

0

3

ЧИСЛО перестановок РЯДКІВ = 1

РІШЕННЯ невязкую X (В-АХ) 316667 0

-183333                      0

.333333 436557Е-11

END AT  LINE  660

Джерело: Уолш Б Програмування на Бейсике: Пер з англ М: Радіо і звязок, 1988 336 с: ил

Схожі статті:


Сподобалася стаття? Ви можете залишити відгук або підписатися на RSS , щоб автоматично отримувати інформацію про нові статтях.

Коментарів поки що немає.

Ваш отзыв

Поділ на параграфи відбувається автоматично, адреса електронної пошти ніколи не буде опублікований, допустимий HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*

*