5.3: Поворотний

У нашому описі алгоритму гаусової елімінації до цих пір ви, можливо, помітили проблему. Під час процесу скорочення рядків ми повинні помножити рядки на коефіцієнт$A'_{mn}/A'_{nn}$ (де$\mathbf{A}'$ позначає поточну матрицю). Якщо$A'_{nn}$ трапляється нуль, коефіцієнт виривається, і алгоритм виходить з ладу.

Щоб обійти цю складність, додаємо додатковий крок до процедури зменшення рядів. Коли ми крокуємо вперед через номери рядків$n = 0, 1, \cdots, N-1$, ми робимо наступне для кожного$n$:

• Поворотні: пошук елементів матриці на і нижче діагонального елемента в$(n,n)$, і знайти рядок$n'$ з найбільшим значенням$|A'_{n'n}|$. Потім поміняти місцями ряд$n$ і ряд$n'$.
• Продовжуйте з іншим алгоритмом, усунувши$A'_{mn}$ елементи нижче діагоналі.

Ви повинні бути в змозі переконати себе, що (i) поворот не змінює рішення, і (ii) це не змінює масштабування часу виконання фази скорочення рядків, яка залишається$O(N^3)$.

Окрім запобігання надмірному виходу алгоритму з ладу, поворот покращує його числову стабільність. Якщо$A'_{nn}$ ненульовий, але дуже малий за величиною, поділ на нього дасть дуже великий результат, що призводить до втрати числової точності з плаваючою комою. Отже, вигідно міняти місцями ряди навколо, щоб гарантувати, що$A'_{nn}$ величина була якомога більшою.

При спробі повороту може статися, що всі значення діагоналі та нижче діагоналі дорівнюють нулю (або досить близькі до нуля в межах нашого допуску з плаваючою$|A'_{n'n}|$ комою). Якщо це станеться, то це вказує на те, що наша вихідна$\mathbf{A}$ матриця є одниною, тобто вона не має зворотного. Отже, процедура повороту має додаткову перевагу, допомагаючи нам вловити випадки, коли немає дійсного рішення системи рівнянь; у таких випадках алгоритм гаусової елімінації повинен перервати.

5.3.1 Приклад

Давайте попрацюємо на прикладі гаусової елімінації з поворотом, використовуючи задачу в попередньому розділі:

$$\left[\begin{array}{ccc|cc} 1 & 2 & 3 & 3 & 6 \\ 3 & 2 & 2 & 4 & 8 \\ 2 & 6 & 2 & 4 & 2 \end{array}\right].$$

Фаза скорочення рядів йде наступним чином:

• ($n=0$): Pivot, міняючи рядки$0$ та рядки$1$:
  $$\left[\begin{array}{ccc|cc} 3 & 2 & 2 & 4 & 8 \\ 1 & 2 & 3 & 3 & 6 \\ 2 & 6 & 2 & 4 & 2 \end{array}\right].$$
• ($n=0$): Усунути елемент за адресою$(1,0)$:
  $$\left[\begin{array}{ccc|cc} 3 & 2 & 2 & 4 & 8 \\ 0 & 4/3 & 7/3 & 5/3 & 10/3 \\ 2 & 6 & 2 & 4 & 2 \end{array}\right].$$
• ($n=0$): Усунути елемент за адресою$(2,0)$:
  $$\left[\begin{array}{ccc|cc} 3 & 2 & 2 & 4 & 8 \\ 0 & 4/3 & 7/3 & 5/3 & 10/3 \\ 0 & 14/3 & 2/3 & 4/3 & -10/3 \end{array}\right].$$
• ($n=1$): Pivot, міняючи рядки$1$ та рядки$2$:
  $$\left[\begin{array}{ccc|cc} 3 & 2 & 2 & 4 & 8 \\ 0 & 14/3 & 2/3 & 4/3 & -10/3 \\0 & 4/3 & 7/3 & 5/3 & 10/3 \end{array}\right].$$
• ($n=1$): Усунути елемент за адресою$(2,1)$:
  $$\left[\begin{array}{ccc|cc} 3 & 2 & 2 & 4 & 8 \\ 0 & 14/3 & 2/3 & 4/3 & -10/3 \\0 & 0 & 15/7 & 9/7 & 30/7 \end{array}\right].$$

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