8: Метод Гаусса-Зайделя

Цілі навчання

Прочитавши цю главу, ви повинні мати можливість:

1. вирішувати множину рівнянь методом Гауса-Зайделя,
2. визнати переваги і підводні камені методу Гаусса-Зайделя, і
3. визначити, за яких умов завжди сходиться метод Гаусса-Зайделя.

Навіщо потрібен інший метод для вирішення безлічі одночасних лінійних рівнянь?

У певних випадках, наприклад, коли система рівнянь велика, ітераційні методи розв'язання рівнянь більш вигідні. Методи ліквідації, такі як гаусова елімінація, схильні до великих похибок округлення для великого набору рівнянь. Ітераційні методи, такі як метод Гаусса-Зайделя, дають користувачеві контроль над помилкою округлення. Крім того, якщо фізика задачі добре відома, початкові здогадки, необхідні в ітераційних методах, можуть бути зроблені більш розумно, що призводять до більш швидкої збіжності.

Який алгоритм для методу Гауса-Зайделя? З огляду на загальний набір$n$ рівнянь і$n$ невідомих, ми маємо

$$a_{11}x_{1} + a_{12}x_{2} + a_{13}x_{3} + ... + a_{1n}x_{n} = c_{1} \nonumber$$

$$a_{21}x_{1} + a_{22}x_{2} + a_{23}x_{3} + ... + a_{2n}x_{n} = c_{2} \nonumber$$

$$\vdots \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \vdots \nonumber$$

$$a_{n1}x_{1} + a_{n2}x_{2} + a_{n3}x_{3} + ... + a_{nn}x_{n} = c_{n} \nonumber$$

Якщо діагональні елементи ненульові, кожне рівняння переписується на відповідне невідоме, тобто перше рівняння переписується з$x_{1}$ лівого боку, друге рівняння переписується з$x_{2}$ лівої сторони і так далі наступним чином

$$x_{1} = \frac{c_{1} - a_{12}x_{2} - a_{13}x_{3}\ldots\ldots - a_{1n}x_{n}}{a_{11}} \nonumber$$

$$x_{2} = \frac{c_{2} - a_{21}x_{1} - a_{23}x_{3}\ldots\ldots - a_{2n}x_{n}}{a_{22}} \nonumber$$

$$\vdots \nonumber$$

$$\vdots \nonumber$$

$$x_{n - 1} = \frac{c_{n - 1} - a_{n - 1,1}x_{1} - a_{n - 1,2}x_{2}\ldots\ldots - a_{n - 1,n - 2}x_{n - 2} - a_{n - 1,n}x_{n}}{a_{n - 1,n - 1}} \nonumber$$

$$x_{n} = \frac{c_{n} - a_{n1}x_{1} - a_{n2}x_{2} - \ldots\ldots - a_{n,n - 1}x_{n - 1}}{a_{nn}} \nonumber$$

Ці рівняння можуть бути переписані у вигляді підсумовування як

$$x_{1} = \frac{c_{1} - \sum_{\begin{matrix} j = 1 \\ j \neq 1 \\ \end{matrix}}^{n}{a_{1j}x_{j}}}{a_{11}} \nonumber$$

$$x_{2} = \frac{c_{2} - \sum_{\begin{matrix} j = 1 \\ j \neq 2 \\ \end{matrix}}^{n}a_{2j}x_{j}}{a_{22}} \nonumber$$

$$\vdots \nonumber$$

$$x_{n - 1} = \frac{c_{n - 1} - \sum_{\begin{matrix} j = 1 \\ j \neq n - 1 \\ \end{matrix}}^{n}{a_{n - 1,j}x_{j}}}{a_{n - 1,n - 1}} \nonumber$$

$$x_{n} = \frac{c_{n} - \sum_{\begin{matrix} j = 1 \\ j \neq n \\ \end{matrix}}^{n}{a_{nj}x_{j}}}{a_{nn}} \nonumber$$

Значить для будь-якого ряду$i$,

$$x_{i} = \frac{c_{i} - \sum_{\begin{matrix} j = 1 \\ j \neq i \\ \end{matrix}}^{n}{a_{ij}x_{j}}}{a_{ii}},i = 1,2,\ldots,n. \nonumber$$

Тепер, щоб знайти$x_{i}$ 's, один припускає початкове припущення для$x_{i}$' s, а потім використовує переписані рівняння для обчислення нових оцінок. Пам'ятайте, що завжди використовуються найновіші оцінки для обчислення наступних оцінок,$x_{i}$. Наприкінці кожної ітерації обчислюється абсолютна відносна приблизна похибка для кожної$x_{i}$ як

$$\left| \in_{a} \right|_{i} = \left| \frac{x_{i}^{\text{new}} - x_{i}^{\text{old}}}{x_{i}^{\text{new}}} \right| \times 100 \nonumber$$

де$x_{i}^{\text{new}}$ - нещодавно отримане значення$x_{i}$, і$x_{i}^{\text{old}}$ є попереднім значенням$x_{i}$.

Коли абсолютна відносна приблизна похибка для кожного$x_{i}$ менше, ніж попередньо заданий допуск, ітерації зупиняються.

Приклад 1

Швидкість вгору ракети наведена в три різні часи в наступній таблиці.

Таблиця 1: Дані про швидкість проти часу.

Час,$t (s)$	Швидкість,$v (m/s)$
\ (t (s)\) ">5	\ (v (м/с)\) ">106.8
\ (t (s)\) ">8	\ (v (м/с)\) ">177.2
\ (t (s)\) ">12	\ (v (м/с)\) ">279.2

Дані про швидкість наближаються поліномом як

$$v\left( t \right) = a_{1}t^{2} + a_{2}t + a_{3},5 \leq t \leq 12 \nonumber$$

Знайти значення за$a_{1},\ a_{2},and \ a_{3}$ допомогою методу Гаусса-Зайделя. Припустімо початкове припущення рішення як

$$\begin{bmatrix} a_{1} \\ a_{2} \\ a_{3} \\ \end{bmatrix} = \begin{bmatrix} 1 \\ 2 \\ 5 \\ \end{bmatrix} \nonumber$$

і провести дві ітерації.

Рішення

Многочлен проходить через три точки даних,$\left( t_{1},v_{1} \right),\left( t_{2},v_{2} \right),and\left( t_{3},v_{3} \right)$ звідки з наведеної вище таблиці.

$$t_{1} = 5,v_{1} = 106.8 \nonumber$$

$$t_{2} = 8,v_{2} = 177.2 \nonumber$$

$$t_{3} = 12,v_{3} = 279.2 \nonumber$$

Вимога, що$v\left( t \right) = a_{1}t^{2} + a_{2}t + a_{3}$ проходить через три точки даних дає

$$v\left( t_{1} \right) = v_{1} = a_{1}t_{1}^{2} + a_{2}t_{1} + a_{3} \nonumber$$

$$v\left( t_{2} \right) = v_{2} = a_{1}t_{2}^{2} + a_{2}t_{2} + a_{3} \nonumber$$

$$v\left( t_{3} \right) = v_{3} = a_{1}t_{3}^{2} + a_{2}t_{3} + a_{3} \nonumber$$

Підстановка даних$\left( t_{1},v_{1} \right),\left( t_{2},v_{2} \right),and\left( t_{3},v_{3} \right)$ дає

$$a_{1}\left( 5^{2} \right) + a_{2}\left( 5 \right) + a_{3} = 106.8 \nonumber$$

$$a_{1}\left( 8^{2} \right) + a_{2}\left( 8 \right) + a_{3} = 177.2 \nonumber$$

$$a_{1}\left( 12^{2} \right) + a_{2}\left( 12 \right) + a_{3} = 279.2 \nonumber$$

або

$$25a_{1} + 5a_{2} + a_{3} = 106.8 \nonumber$$

$$64a_{1} + 8a_{2} + a_{3} = 177.2 \nonumber$$

$$144a_{1} + 12a_{2} + a_{3} = 279.2 \nonumber$$

Коефіцієнти$a_{1},a_{2},anda_{3}$ для вищевказаного виразу задаються

$$\begin{bmatrix} 25 & 5 & 1 \\ 64 & 8 & 1 \\ 144 & 12 & 1 \\ \end{bmatrix}\begin{bmatrix} a_{1} \\ a_{2} \\ a_{3} \\ \end{bmatrix} = \begin{bmatrix} 106.8 \\ 177.2 \\ 279.2 \\ \end{bmatrix} \nonumber$$

Переписування рівнянь дає

$$a_{1} = \frac{106.8 - 5a_{2} - a_{3}}{25} \nonumber$$

$$a_{2} = \frac{177.2 - 64a_{1} - a_{3}}{8} \nonumber$$

$$a_{3} = \frac{279.2 - 144a_{1} - 12a_{2}}{1} \nonumber$$

Ітерація #1

Задано початкове припущення вектора розв'язку як

$$\begin{bmatrix} a_{1} \\ a_{2} \\ a_{3} \\ \end{bmatrix} = \begin{bmatrix} 1 \\ 2 \\ 5 \\ \end{bmatrix} \nonumber$$

отримуємо

$$\begin{split} a_{1} &= \frac{106.8 - 5(2) - (5)}{25}\\ &= 3.6720 \end{split} \nonumber$$

$$\begin{split} a_{2} &= \frac{177.2 - 64\left( 3.6720 \right) - \left( 5 \right)}{8}\\ &= - 7.8150 \end{split} \nonumber$$

$$\begin{split} a_{3} &= \frac{279.2 - 144\left( 3.6720 \right) - 12\left( - 7.8510 \right)}{1}\\ &= - 155.36 \end{split} \nonumber$$

Абсолютна відносна приблизна похибка для кожного$x_{i}$ тоді дорівнює

$$\begin{split} \left| \in_{a} \right|_{1} &= \left| \frac{3.6720 - 1}{3.6720} \right| \times 100\\ &= 72.76\% \end{split} \nonumber$$

$$\begin{split} \left| \in_{a} \right|_{2} &= \left| \frac{- 7.8510 - 2}{- 7.8510} \right| \times 100\\ &= 125.47\% \end{split} \nonumber$$

$$\begin{split} \left| \in_{a} \right|_{3} &= \left| \frac{- 155.36 - 5}{- 155.36} \right| \times 100\\ &= 103.22\% \end{split} \nonumber$$

В кінці першої ітерації оцінка вектора розв'язку дорівнює

$$\begin{bmatrix} a_{1} \\ a_{2} \\ a_{3} \\ \end{bmatrix} = \begin{bmatrix} 3.6720 \\ - 7.8510 \\ - 155.36 \\ \end{bmatrix} \nonumber$$

і максимальна абсолютна відносна приблизна похибка дорівнює$125.47%$.

Ітерація #2

Оцінка вектора розв'язку в кінці Ітерації #1 дорівнює

$$\begin{bmatrix} a_{1} \\ a_{2} \\ a_{3} \\ \end{bmatrix} = \begin{bmatrix} 3.6720 \\ - 7.8510 \\ - 155.36 \\ \end{bmatrix} \nonumber$$

Тепер отримуємо

$$\begin{split} a_{1} &= \frac{106.8 - 5\left( - 7.8510 \right) - ( - 155.36)}{25}\\ &= 12.056 \end{split} \nonumber$$

$$\begin{split} a_{2} &= \frac{177.2 - 64\left( 12.056 \right) - ( - 155.36)}{8}\\ &= - 54.882 \end{split} \nonumber$$

$$\begin{split} a_{3} &= \frac{279.2 - 144\left( 12.056 \right) - 12\left( - 54.882 \right)}{1}\\ &= - 798.34 \end{split} \nonumber$$

Абсолютна відносна приблизна похибка для кожного$x_{i}$ тоді дорівнює

$$\begin{split} \left| \in_{a} \right|_{1} &= \left| \frac{12.056 - 3.6720}{12.056} \right| \times 100\\ &= 69.543\% \end{split} \nonumber$$

$$\begin{split} \left| \in_{a} \right|_{2} &= \left| \frac{- 54.882 - \left( - 7.8510 \right)}{- 54.882} \right| \times 100\\ &= 85.695\% \end{split} \nonumber$$

$$\begin{split} \left| \in_{a} \right|_{3} &= \left| \frac{- 798.34 - \left( - 155.36 \right)}{- 798.34} \right| \times 100\\ &= 80.540\% \end{split} \nonumber$$

В кінці другої ітерації оцінка вектора розв'язку дорівнює

$$\begin{bmatrix} a_{1} \\ a_{2} \\ a_{3} \\ \end{bmatrix} = \begin{bmatrix} 12.056 \\ - 54.882 \\ - 798.54 \\ \end{bmatrix} \nonumber$$

і максимальна абсолютна відносна приблизна похибка дорівнює$85.695\%$.

Проведення більшої кількості ітерацій дає наступні значення вектора розв'язку та відповідні абсолютні відносні наближені похибки.

Ітерація	$a_{1}$	$\left| \in_{a} \right|_{1} \%$	$a_{2}$	$\left| \in_{a} \right|_{2} \%$	$a_{3}$	$\left| \in_{a} \right|_{3} \%$
1	\ (a_ {1}\) ">3.672	\ (\ ліворуч |\ in_ {a}\ праворуч |_ {1}\%\) ">72.767	\ (a_ {2}\) ">—7.8510	\ (\ ліворуч |\ in_ {a}\ праворуч |_ {2}\%\) ">125.47	\ (a_ {3}\) ">—155.36	\ (\ ліворуч |\ in_ {a}\ праворуч |_ {3}\%\) ">103.22
2	\ (a_ {1}\) ">12.056	\ (\ ліворуч |\ in_ {a}\ праворуч |_ {1}\%\) ">69.543	\ (a_ {2}\) ">—54.882	\ (\ ліворуч |\ in_ {a}\ праворуч |_ {2}\%\) ">85.695	\ (a_ {3}\) ">—798.34	\ (\ ліворуч |\ in_ {a}\ праворуч |_ {3}\%\) ">80.54
3	\ (a_ {1}\) ">47.182	\ (\ ліворуч |\ in_ {a}\ праворуч |_ {1}\%\) ">74.447	\ (a_ {2}\) ">—255.51	\ (\ ліворуч |\ in_ {a}\ праворуч |_ {2}\%\) ">78.521	\ (a_ {3}\) ">—3448.9	\ (\ ліворуч |\ in_ {a}\ праворуч |_ {3}\%\) ">76.852
4	\ (a_ {1}\) ">193.33	\ (\ ліворуч |\ in_ {a}\ праворуч |_ {1}\%\) ">75.595	\ (a_ {2}\) ">—1093.4	\ (\ ліворуч |\ in_ {a}\ праворуч |_ {2}\%\) ">76.632	\ (a_ {3}\) ">—14440	\ (\ ліворуч |\ in_ {a}\ праворуч |_ {3}\%\) ">76.116
5	\ (a_ {1}\) ">800.53	\ (\ ліворуч |\ in_ {a}\ праворуч |_ {1}\%\) ">75.85	\ (a_ {2}\) ">—4577.2	\ (\ ліворуч |\ in_ {a}\ праворуч |_ {2}\%\) ">76.112	\ (a_ {3}\) ">—60072	\ (\ ліворуч |\ in_ {a}\ праворуч |_ {3}\%\) ">75.963
6	\ (a_ {1}\) ">3322.6	\ (\ ліворуч |\ in_ {a}\ праворуч |_ {1}\%\) ">75.906	\ (a_ {2}\) ">—19049	\ (\ ліворуч |\ in_ {a}\ праворуч |_ {2}\%\) ">75.972	\ (a_ {3}\) ">—249580	\ (\ ліворуч |\ in_ {a}\ праворуч |_ {3}\%\) ">75.931

Як видно з наведеної вище таблиці, оцінки рішення не сходяться до істинного рішення

$$a_{1} = 0.29048 \nonumber$$

$$a_{2} = 19.690 \nonumber$$

$$a_{3} = 1.0857 \nonumber$$

Наведена вище система рівнянь, схоже, не сходиться. Чому?

Ну, підводним каменем більшості ітераційних методів є те, що вони можуть або не можуть сходитися. Однак рішення певного класу системи одночасних рівнянь завжди сходиться за допомогою методу Гаусса-Зайделя. Цей клас системи рівнянь - це де матриця коефіцієнтів$\lbrack A\rbrack$ в$\lbrack A\rbrack\lbrack X\rbrack = \lbrack C\rbrack$ діагонально домінуюча, тобто

$$\left| a_{ii} \right| \geq \sum_{\begin{matrix} j = 1 \\ j \neq i \\ \end{matrix}}^{n}\left| a_{ij} \right|\ \text{for all }i \nonumber$$

$$\left| a_{ii} \right| > \sum_{\begin{matrix} j = 1 \\ j \neq i \\ \end{matrix}}^{n}\left| a_{ij} \right|\text{for at least one }i \nonumber$$

Якщо система рівнянь має матрицю коефіцієнтів, яка не є домінуючою по діагоналі, вона може сходитися або не сходитися. На щастя, багато фізичних систем, що призводять до одночасних лінійних рівнянь, мають діагонально домінуючу матрицю коефіцієнтів, яка потім забезпечує збіжність для ітераційних методів, таких як метод Гаусса-Зайделя розв'язування одночасних лінійних рівнянь.

Приклад 2

Знайти розв'язок наступної системи рівнянь за допомогою методу Гаусса-Зайделя.

$$12x_{1} + 3x_{2} - 5x_{3} = 1 \nonumber$$

$$x_{1} + 5x_{2} + 3x_{3} = 28 \nonumber$$

$$3x_{1} + 7x_{2} + 13x_{3} = 76 \nonumber$$

Використовувати

$$\begin{bmatrix} x_{1} \\ x_{2} \\ x_{3} \\ \end{bmatrix} = \begin{bmatrix} 1 \\ 0 \\ 1 \\ \end{bmatrix} \nonumber$$

як початкове вгадати і провести дві ітерації.

Рішення 1

матриця коефіцієнтів

$$\left\lbrack A \right\rbrack = \begin{bmatrix} 12 & 3 & - 5 \\ 1 & 5 & 3 \\ 3 & 7 & 13 \\ \end{bmatrix} \nonumber$$

є діагонально домінуючим як

$$\left| a_{11} \right| = \left| 12 \right| = 12 \geq \left| a_{12} \right| + \left| a_{13} \right| = \left| 3 \right| + \left| - 5 \right| = 8 \nonumber$$

$$\left| a_{22} \right| = \left| 5 \right| = 5 \geq \left| a_{21} \right| + \left| a_{23} \right| = \left| 1 \right| + \left| 3 \right| = 4 \nonumber$$

$$\left| a_{33} \right| = \left| 13 \right| = 13 \geq \left| a_{31} \right| + \left| a_{32} \right| = \left| 3 \right| + \left| 7 \right| = 10 \nonumber$$

і нерівність строго більше, ніж для хоча б одного ряду. Значить, розчин повинен сходитися за методом Гауса-Зайделя.

Переписуючи рівняння, отримуємо

$$x_{1} = \frac{1 - 3x_{2} + 5x_{3}}{12} \nonumber$$

$$x_{2} = \frac{28 - x_{1} - 3x_{3}}{5} \nonumber$$

$$x_{3} = \frac{76 - 3x_{1} - 7x_{2}}{13} \nonumber$$

Припускаючи початкове припущення

$$\begin{bmatrix} x_{1} \\ x_{2} \\ x_{3} \\ \end{bmatrix} = \begin{bmatrix} 1 \\ 0 \\ 1 \\ \end{bmatrix} \nonumber$$

Ітерація #1

$$\begin{split} x_{1} &= \frac{1 - 3\left( 0 \right) + 5\left( 1 \right)}{12}\\ & = 0.50000 \end{split} \nonumber$$

$$\begin{split} x_{2} &= \frac{28 - \left( 0.50000 \right) - 3\left( 1 \right)}{5}\\ &= 4.9000 \end{split} \nonumber$$

$$\begin{split} x_{3} &= \frac{76 - 3\left( 0.50000 \right) - 7\left( 4.9000 \right)}{13}\\ &= 3.0923 \end{split} \nonumber$$

Абсолютна відносна приблизна похибка в кінці першої ітерації дорівнює

$$\begin{split} \left| \in_{a} \right|_{1} &= \left| \frac{0.50000 - 1}{0.50000} \right| \times 100\\ &= 100.00\% \end{split} \nonumber$$

$$\begin{split} \left| \in_{a} \right|_{2} &= \left| \frac{4.9000 - 0}{4.9000} \right| \times 100\\ &= 100.00\% \end{split} \nonumber$$

$$\begin{split} \left| \in_{a} \right|_{3} &= \left| \frac{3.0923 - 1}{3.0923} \right| \times 100\\ &= 67.662\% \end{split} \nonumber$$

Максимальна абсолютна відносна приблизна похибка дорівнює$100.00\%$

Ітерація #2

$$\begin{split} x_{1} &= \frac{1 - 3\left( 4.9000 \right) + 5\left( 3.0923 \right)}{12}\\ &= 0.14679 \end{split} \nonumber$$

$$\begin{split} x_{2} &= \frac{28 - \left( 0.14679 \right) - 3\left( 3.0923 \right)}{5}\\ &= 3.7153 \end{split} \nonumber$$

$$\begin{split} x_{3} &= \frac{76 - 3\left( 0.14679 \right) - 7\left( 3.7153 \right)}{13}\\ &= 3.8118 \end{split} \nonumber$$

В кінці другої ітерації абсолютна відносна приблизна похибка дорівнює

$$\begin{split} \left| \in_{a} \right|_{1} &= \left| \frac{0.14679 - 0.50000}{0.14679} \right| \times 100\\ &= 240.61\% \end{split} \nonumber$$

$$\begin{split} \left| \in_{a} \right|_{2} &= \left| \frac{3.7153 - 4.9000}{3.7153} \right| \times 100\\ &= 31.889\% \end{split} \nonumber$$

$$\begin{split} \left| \in_{a} \right|_{3} &= \left| \frac{3.8118 - 3.0923}{3.8118} \right| \times 100\\ &= 18.874\% \end{split} \nonumber$$

Максимальна абсолютна відносна приблизна похибка дорівнює$240.61\%$. Це більше, ніж значення, отримане$100.00\%$ нами в першій ітерації. Рішення розходиться? Ні, оскільки ви проводите більше ітерацій, рішення сходиться наступним чином.

Ітерація	$a_{1}$	$\left| \in_{a} \right|_{1} \%$	$a_{2}$	$\left| \in_{a} \right|_{2} \%$	$a_{3}$	$\left| \in_{a} \right|_{3} \%$
1	\ (a_ {1}\) ">0.5	\ (\ ліворуч |\ in_ {a}\ праворуч |_ {1}\%\) ">100	\ (a_ {2}\) ">4.9	\ (\ ліворуч |\ in_ {a}\ праворуч |_ {2}\%\) ">100	\ (a_ {3}\) ">3.0923	\ (\ ліворуч |\ in_ {a}\ праворуч |_ {3}\%\) ">67.662
2	\ (a_ {1}\) ">0.14679	\ (\ ліворуч |\ in_ {a}\ праворуч |_ {1}\%\) ">240.61	\ (a_ {2}\) ">3.7153	\ (\ ліворуч |\ in_ {a}\ праворуч |_ {2}\%\) ">31.889	\ (a_ {3}\) ">3.8118	\ (\ ліворуч |\ in_ {a}\ праворуч |_ {3}\%\) ">18.874
3	\ (a_ {1}\) ">0.74275	\ (\ ліворуч |\ in_ {a}\ праворуч |_ {1}\%\) ">80.236	\ (a_ {2}\) ">3.1644	\ (\ ліворуч |\ in_ {a}\ праворуч |_ {2}\%\) ">17.408	\ (a_ {3}\) ">3.9708	\ (\ ліворуч |\ in_ {a}\ праворуч |_ {3}\%\) ">4.0064
4	\ (a_ {1}\) ">0.94675	\ (\ ліворуч |\ in_ {a}\ праворуч |_ {1}\%\) ">21.546	\ (a_ {2}\) ">3.0281	\ (\ ліворуч |\ in_ {a}\ праворуч |_ {2}\%\) ">4.4996	\ (a_ {3}\) ">3.9971	\ (\ ліворуч |\ in_ {a}\ праворуч |_ {3}\%\) ">0.65772
5	\ (a_ {1}\) ">0.99177	\ (\ ліворуч |\ in_ {a}\ праворуч |_ {1}\%\) ">4.5391	\ (a_ {2}\) ">3.0034	\ (\ ліворуч |\ in_ {a}\ праворуч |_ {2}\%\) ">0.82499	\ (a_ {3}\) ">4.0001	\ (\ ліворуч |\ in_ {a}\ праворуч |_ {3}\%\) ">0.074383
6	\ (a_ {1}\) ">0.99919	\ (\ ліворуч |\ in_ {a}\ праворуч |_ {1}\%\) ">0.74307	\ (a_ {2}\) ">3.0001	\ (\ ліворуч |\ in_ {a}\ праворуч |_ {2}\%\) ">0.10856	\ (a_ {3}\) ">4.0001	\ (\ ліворуч |\ in_ {a}\ праворуч |_ {3}\%\) ">0.00101

Це близько до точного вектора розв'язку

$$\begin{bmatrix} x_{1} \\ x_{2} \\ x_{3} \\ \end{bmatrix} = \begin{bmatrix} 1 \\ 3 \\ 4 \\ \end{bmatrix} \nonumber$$

Приклад 3

Задано систему рівнянь

$$3x_{1} + 7x_{2} + 13x_{3} = 76 \nonumber$$

$$x_{1} + 5x_{2} + 3x_{3} = 28 \nonumber$$

$$12x_{1} + 3x_{2} - 5x_{3} = 1 \nonumber$$

знайти рішення за допомогою методу Гауса-Зайделя. Використовувати

$$\begin{bmatrix} x_{1} \\ x_{2} \\ x_{3} \\ \end{bmatrix} = \begin{bmatrix} 1 \\ 0 \\ 1 \\ \end{bmatrix} \nonumber$$

як початкова здогадка.

Рішення 1

Переписуючи рівняння, отримуємо

$$x_{1} = \frac{76 - 7x_{2} - 13x_{3}}{3} \nonumber$$

$$x_{2} = \frac{28 - x_{1} - 3x_{3}}{5} \nonumber$$

$$x_{3} = \frac{1 - 12x_{1} - 3x_{2}}{- 5} \nonumber$$

Припускаючи початкове припущення

$$\begin{bmatrix} x_{1} \\ x_{2} \\ x_{3} \\ \end{bmatrix} = \begin{bmatrix} 1 \\ 0 \\ 1 \\ \end{bmatrix} \nonumber$$

наступні шість ітераційних значень наведені в таблиці нижче.

Ітерація	$a_{1}$	$\left| \in_{a} \right|_{1} \%$	$a_{2}$	$\left| \in_{a} \right|_{2} \%$	$a_{3}$	$\left| \in_{a} \right|_{3} \%$
1	\ (a_ {1}\) ">21	\ (\ ліворуч |\ in_ {a}\ праворуч |_ {1}\%\) ">95.238	\ (a_ {2}\) ">0.8	\ (\ ліворуч |\ in_ {a}\ праворуч |_ {2}\%\) ">100	\ (a_ {3}\) ">50.68	\ (\ ліворуч |\ in_ {a}\ праворуч |_ {3}\%\) ">98.027
2	\ (a_ {1}\) ">—196.15	\ (\ ліворуч |\ in_ {a}\ праворуч |_ {1}\%\) ">110.71	\ (a_ {2}\) ">14.421	\ (\ ліворуч |\ in_ {a}\ праворуч |_ {2}\%\) ">94.453	\ (a_ {3}\) ">—462.30	\ (\ ліворуч |\ in_ {a}\ праворуч |_ {3}\%\) ">110.96
3	\ (a_ {1}\) ">1995	\ (\ ліворуч |\ in_ {a}\ праворуч |_ {1}\%\) ">109.83	\ (a_ {2}\) ">—116.02	\ (\ ліворуч |\ in_ {a}\ праворуч |_ {2}\%\) ">112.43	\ (a_ {3}\) ">4718.1	\ (\ ліворуч |\ in_ {a}\ праворуч |_ {3}\%\) ">109.8
4	\ (a_ {1}\) ">—20149	\ (\ ліворуч |\ in_ {a}\ праворуч |_ {1}\%\) ">109.9	\ (a_ {2}\) ">1204.6	\ (\ ліворуч |\ in_ {a}\ праворуч |_ {2}\%\) ">109.63	\ (a_ {3}\) ">—47636	\ (\ ліворуч |\ in_ {a}\ праворуч |_ {3}\%\) ">109.9
5	\ (a_ {1}\) ">2.0364$\times 10^5$	\ (\ ліворуч |\ in_ {a}\ праворуч |_ {1}\%\) ">109.89	\ (a_ {2}\) ">—12140	\ (\ ліворуч |\ in_ {a}\ праворуч |_ {2}\%\) ">109.92	\ (a_ {3}\) ">4.8144$\times 10^5$	\ (\ ліворуч |\ in_ {a}\ праворуч |_ {3}\%\) ">109.89
6	\ (a_ {1}\) ">—2.0579$\times 10^6$	\ (\ ліворуч |\ in_ {a}\ праворуч |_ {1}\%\) ">109.89	\ (a_ {2}\) ">1.2272$\times 10^5$	\ (\ ліворуч |\ in_ {a}\ праворуч |_ {2}\%\) ">109.89	\ (a_ {3}\) ">—4.8653$\times 10^6$	\ (\ ліворуч |\ in_ {a}\ праворуч |_ {3}\%\) ">109.89

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

$$\left\lbrack A \right\rbrack = \begin{bmatrix} 3 & 7 & 13 \\ 1 & 5 & 3 \\ 12 & 3 & - 5 \\ \end{bmatrix} \nonumber$$

не є домінуючим по діагоналі, як

$$\left| a_{11} \right| = \left| 3 \right| = 3 \leq \left| a_{12} \right| + \left| a_{13} \right| = \left| 7 \right| + \left| 13 \right| = 20 \nonumber$$

Значить, метод Гауса-Зайделя може сходитися, а може і не сходитися.

Однак це той самий набір рівнянь, що і попередній приклад, і який сходився. Єдина відмінність полягає в тому, що ми обмінялися першим і третім рівнянням один з одним, і це зробило матрицю коефіцієнтів не домінуючою по діагоналі.

Тому не виключено, що система рівнянь може бути зроблена діагонально домінуючою, якщо обмінюватися рівняннями один з одним. Однак це можливо не для всіх випадків. Наприклад, наступний набір рівнянь

$$x_{1} + x_{2} + x_{3} = 3 \nonumber$$

$$2x_{1} + 3x_{2} + 4x_{3} = 9 \nonumber$$

$$x_{1} + 7x_{2} + x_{3} = 9 \nonumber$$

неможливо переписати, щоб зробити матрицю коефіцієнтів по діагоналі домінуючою.

Вікторина методу Гауса-Зайделя

Вікторина 1

Квадратна матриця$\left\lbrack A \right\rbrack_{n \times n}$ є домінуючою по діагоналі, якщо

(А)$\displaystyle \left| a_{ii} \right| \geq \sum_{\begin{matrix} j = 1 \\ i \neq j \\ \end{matrix}}^{n}\left| a_{ij} \right|$,$i = 1,2,...,n$

(B)$\displaystyle \left| a_{ii} \right| \geq \sum_{\begin{matrix} j = 1 \\ i \neq j \\ \end{matrix}}^{n}\left| a_{ij} \right|,$$i = 1,2,...,n$ і$\left| a_{ii} \right| > \sum_{\begin{matrix} j = 1 \\ i \neq j \\ \end{matrix}}^{n}\left| a_{ij} \right|,$ для будь-якого$i = 1,2,...,n$

(C)$\displaystyle \left| a_{ii} \right| \geq \sum_{j = 1}^{n}\left| a_{ij} \right|,$$i = 1,2,...,n$ і$\left| a_{ii} \right| > \sum_{j = 1}^{n}\left| a_{ij} \right|,$ для будь-якого$i = 1,2,...,n$

(D)$\displaystyle \left| a_{ii} \right| \geq \sum_{j = 1}^{n}\left| a_{ij} \right|,$$i = 1,2,...,n$

Вікторина 2

Використовуючи$\lbrack x_{1},x_{2},x_{3}\rbrack = \lbrack 1,3,5\rbrack$ як початкову здогадку, значення$\lbrack x_{1},x_{2},x_{3}\rbrack$ після трьох ітерацій у методі Гаусса-Зайделя для

$$\begin{bmatrix} 12 & 7 & 3 \\ 1 & 5 & 1 \\ 2 & 7 & - 11 \\ \end{bmatrix}\begin{bmatrix} x_{1} \\ x_{2} \\ x_{3} \\ \end{bmatrix} = \begin{bmatrix} 2 \\ - 5 \\ 6 \\ \end{bmatrix} \nonumber$$

є

(А)$[-2.8333 -1.4333 -1.9727]$

(Б)$[1.4959 -0.90464 -0.84914]$

(С)$[0.90666 -1.0115 -1.0243]$

(D)$[1.2148 -0.72060 -0.82451]$

Вікторина 3

Для того, щоб наступна система рівнянь,

$$\begin{matrix} 2x_{1} + & 7x_{2} - & 11x_{3} = & 6 \\ x_{1} + & 2x_{2} + & x_{3} = & - 5 \\ 7x_{1} + & 5x_{2} + & 2x_{3} = & 17 \\ \end{matrix} \nonumber$$

сходиться за допомогою методу Гаусса-Зайделя, можна переписати вищевказані рівняння наступним чином:

(А)$\begin{bmatrix} 2 & 7 & - 11 \\ 1 & 2 & 1 \\ 7 & 5 & 2 \\ \end{bmatrix}\ \begin{bmatrix} x_{1} \\ x_{2} \\ x_{3} \\ \end{bmatrix} = \begin{bmatrix} 6 \\ -5 \\ 17 \\ \end{bmatrix}$

(Б)$\begin{bmatrix} 7 & 5 & 2 \\ 1 & 2 & 1 \\ 2 & 7 & - 11 \\ \end{bmatrix}\ \begin{bmatrix} x_{1} \\ x_{2} \\ x_{3} \\ \end{bmatrix} = \begin{bmatrix} 17 \\ -5 \\ 6 \\ \end{bmatrix}$

(С)$\begin{bmatrix} 7 & 5 & 2 \\ 1 & 2 & 1 \\ 2 & 7 & - 11 \\ \end{bmatrix}\ \begin{bmatrix} x_{1} \\ x_{2} \\ x_{3} \\ \end{bmatrix} = \begin{bmatrix} 6 \\ -5 \\ 17 \\ \end{bmatrix}$

(D) Рівняння не можна переписати у формі для забезпечення збіжності.

Вікторина 4

Для$\begin{bmatrix} 12 & 7 & 3 \\ 1 & 5 & 1 \\ 2 & 7 & - 11 \\ \end{bmatrix}\ \begin{bmatrix} x_{1} \\ x_{2} \\ x_{3} \\ \end{bmatrix} = \begin{bmatrix} 22 \\ 7 \\ - 2 \\ \end{bmatrix}$ та використання$\begin{bmatrix} x_{1} & x_{2} & x_{3} \\ \end{bmatrix} = \begin{bmatrix} 1 & 2 & 1 \\ \end{bmatrix}$ як початкового припущення значення$\begin{bmatrix} x_{1} & x_{2} & x_{3} \\ \end{bmatrix}$ знаходять в кінці кожної ітерації як

Ітерація #	$x_{1}$	$x_{2}$	$x_{3}$
1	\ (x_ {1}\) ">0.41667	\ (x_ {2}\) ">1.1167	\ (x_ {3}\) ">0.96818
2	\ (x_ {1}\) ">0.93990	\ (x_ {2}\) ">1.0184	\ (x_ {3}\) ">1.0008
3	\ (x_ {1}\) ">0.98908	\ (x_ {2}\) ">1.0020	\ (x_ {3}\) ">0.99931
4	\ (x_ {1}\) ">0.99899	\ (x_ {2}\) ">1.0003	\ (x_ {3}\) ">1.0000

На яке перше число ітерації ви б довіряли принаймні 1 значній цифрі у своєму рішенні?

(А)$1$

(Б)$2$

(С)$3$

(D)$4$

Вікторина 5

Алгоритм розв'язання методу Гаусса-Зайделя$\left\lbrack A \right\rbrack\left\lbrack X \right\rbrack = \left\lbrack C \right\rbrack$ наведено наступним чином при використанні$n\max$ ітерацій. Початкове значення$\left\lbrack X \right\rbrack$ зберігається в$\left\lbrack X \right\rbrack$.

(A) Суб Зайдель$(n,a,x,{rhs},nmax)$ Для$k = 1$ Кому${nmax}$ Для$i = 1$ Кому$n$ Для$j = 1$ Кому$n$ Якщо ($i < > j$) Тоді Сума = Сума +$a(i,j)*x(j)$ кінець Наступний$j$ $x(i) = ( {rhs}(i) - \text{Sum})/a(i,i)$ Наступний$i$ Наступний$j$ Кінець Sub

(Б) Суб Зайдель$(n,a,x,{rhs},nmax)$ Для$k = 1$ Кому${nmax}$ Для$i = 1$ Кому$n$ Сума = 0 Для$j = 1$ Кому$n$ Якщо ($i < > j$) Тоді Сума = Сума +$a(i,j)*x(j)$ кінець Наступний$j$ $x(i) = ( {rhs}(i) - \text{Sum})/a(i,i)$ Наступний$i$ Наступний$k$ Кінець Sub

(C) Суб Зайдель$(n,a,x,{rhs},nmax)$ Для$k = 1$ Кому${nmax}$ Для$i = 1$ Кому$n$ Сума = 0 Для$j = 1$ Кому$n$ Сума = Сума +$a(i,j)*x(j)$ Наступний$j$ $x(i) = ( {rhs}(i) - \text{Sum})/a(i,i)$ Наступний$i$ Наступний$k$ Кінець Sub

(D) Суб Зайдель$(n,a,x,{rhs},nmax)$ Для$k = 1$ Кому {nmax} $ Для$i = 1$ Кому$n$ Сума = 0 Для$j = 1$ Кому$n$ Якщо ($i < > j$) Тоді Сума = Сума +$a(i,j)*x(j)$ кінець Наступний$j$ $x(i) = ( {rhs}(i) - \text{Sum})/a(i,i)$ Наступний$i$ Наступний$k$ Кінець Sub

Вікторина 6

Термістори вимірюють температуру, мають нелінійний вихід і цінуються для обмеженого діапазону. Отже, коли виготовляється термістор, виробник постачає криву опору проти температури. Точне уявлення кривої, як правило, задається

$$\frac{1}{T} = a_{0} + a_{1}ln(R) + a_{2}\left\{ \ln\left( R \right) \right\}^{2} + a_{3}\left\{ \ln\left( R \right) \right\}^{3} \nonumber$$

де$T$ температура в Кельвіні,$R$ - це опір в Омах, і$a_{0},a_{1},a_{2},a_{3}$ є константами калібрувальної кривої. З огляду на наступне для термістора

$R$	$T$
\ (R\) ">Ом	\ (Т\) ">${^\circ}C$
\ (R\) "> 1101.0 911.3 636.0 451.1	\ (Т\) "> 25.113 30.131 40.120 50.128

значення температури в${^\circ}C$ для вимірюваного опору$900$ Ом найбільш майже дорівнює

(А)$30.002$

(Б)$30.473$

(С)$31.272$

(D)$31.445$

Вправа методу Гауса-Зайделя

Вправа 1

У системі рівнянь$[A] [X] = [C]$, якщо$[A]$ діагонально домінантний, то метод Гауссейдала-Зайделя

1. завжди сходиться
2. може сходитися або не сходитися
3. завжди розходиться

Відповідь

A

Вправа 2

У системі$[A] [X] = [C]$ рівнянь якщо не$[A]$ є домінуючою по діагоналі, то метод Гаусса-Зайделя

1. Завжди сходиться
2. Може сходитися або не сходитися
3. Завжди розходиться.

Відповідь

Б

Вправа 3

У системі рівнянь$[A] [X] = [C]$, якщо$[A]$ вона не домінуюча по діагоналі, система рівнянь завжди може бути переписана, щоб зробити її домінуючою по діагоналі.

1. Правда
2. Помилковий

Відповідь

Б

Вправа 4

Розв'яжіть наступну систему рівнянь методом Гауса-Зайделя

$$\begin{matrix} 12x_{1} + 7x_{2} + 3x_{3} = 2 \\ x_{1} + 5x_{2} + x_{3} = - 5 \\ 2x_{1} + 7x_{2} - 11x_{3} = 6 \\ \end{matrix} \nonumber$$

Проведіть 3 ітерації, обчислите максимальну абсолютну відносну приблизну похибку в кінці кожної ітерації і виберіть$\begin{bmatrix} x_{1} & x_{2} & x_{3} \\ \end{bmatrix} = \begin{bmatrix} 1 & 3 & 5 \\ \end{bmatrix}$ як початкову здогадку.

Відповідь

$\begin{bmatrix} x_{1} & x_{2} & x_{3} \\ \end{bmatrix} = \begin{bmatrix} 0.90666 & -1.0115 & -1.0243 \\ \end{bmatrix}$${\begin{bmatrix} \left| \in_{a} \right|_{1} & \left| \in_{a} \right|_{2} & \left| \in_{a} \right|_{3} \\ \end{bmatrix} = \begin{bmatrix} 65.001\% & 10.564\% & 17.099\% \\ \end{bmatrix} }$${\begin{bmatrix} \left| \in_{a} \right|_{1} & \left| \in_{a} \right|_{2} & \left| \in_{a} \right|_{3} \\ \end{bmatrix} = \begin{bmatrix} 65.001\% & 10.564\% & 17.099\% \\ \end{bmatrix} }$

Вправа 5

Розв'яжіть наступну систему рівнянь методом Гауса-Зайделя

$12x_{1} + 7x_{2} + 3x_{3} = 2$
$x_{1} + 5x_{2} + x_{3} = - 5$
$2x_{1} + 7x_{2} - 11x_{3} = 6$
Проведіть 3 ітерації, обчислите максимальну абсолютну відносну приблизну похибку в кінці кожної ітерації та виберіть$\begin{bmatrix} x_{1} & x_{2} & x_{3} \\ \end{bmatrix} = \begin{bmatrix} 1 & 3 & 5 \\ \end{bmatrix}$ як початкову здогадку.

Відповідь

$\begin{bmatrix} x_{1} & x_{2} & x_{3} \\ \end{bmatrix} = \begin{bmatrix} 0.90666 & - 1.0115 & - 1.0243 \\ \end{bmatrix}$

Вправа 6

Вирішіть наступну систему рівнянь методом Гауса-Зайделя
$x_{1} + 5x_{2} + x_{3} = 5$
$12x_{1} + 7x_{2} + 3x_{3} = 2$
$2x_{1} + 7x_{2} - 11x_{3} = 6$
Проведіть 3 ітерації, обчислите максимальну абсолютну відносну наближену похибку в кінці кожної ітерації, і вибрати$\begin{bmatrix} x_{1} & x_{2} & x_{3} \\ \end{bmatrix} = \begin{bmatrix} 1 & 3 & 5 \\ \end{bmatrix}$ в якості початкової здогадки.

Відповідь

$\begin{bmatrix} x_{1} & x_{2} & x_{3} \\ \end{bmatrix} = \begin{bmatrix} -1163.7 & 1947.6 & 1027.2 \\ \end{bmatrix}$

$\begin{bmatrix} \left| \in_{a} \right|_{1} & \left| \in_{a} \right|_{2} & \left| \in_{a} \right|_{3} \\ \end{bmatrix} = \begin{bmatrix} 89.156\% & 89.139\% & 89.183\% \\ \end{bmatrix}$