Пошук опорного елемента (pivoting)

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

Щоб зробити алгоритм який працюють в таких випадках, як раз і існує процес вибору опорного елемента (англійською мовою це називається одним словом "pivoting"). Він полягає в тому, що здійснюється перестановка рядків і/або стовпців матриці, щоб в потрібному елементі a_ii виявилося ненульове число.

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

На щастя, для коректності методу досить одних лише обмінів рядків (т. зв. "partial pivoting", на відміну від "full pivoting", коли обмінюються рядки та стовпці). Але яку ж саме рядок слід вибирати для обміну? І чи правда, що пошук опорного елемента треба робити тільки тоді, коли поточний елемент a_ii нульовий?

Загальної відповіді на це питання не існує. Є різноманітні евристики, однак найефективнішою з них (за співвідношенням простоти і віддачі) є така евристика: в якості опорного елемента слід брати найбільший по модулю елемент, причому проводити пошук опорного елемента і обмін з ним треба завжди, а не тільки коли це необхідно (тобто не тільки тоді, коли a_ii=0).

Іншими словами, перед виконанням i-ої фази алгоритму Гауса-Жордана з евристикою partial pivoting необхідно знайти в i-му стовпці серед елементів із індексами від i до n максимальний по модулю, і обміняти рядок з цим елементом з i-ої рядком.

По-перше, ця евристика дозволить розв'язати СЛАР, навіть якщо по ходу рішення буде траплятися так, що елемент a_ii=0. По-друге, що дуже важливо, ця евристика покращує чисельну стійкість алгоритму Гауса-Жордана.

Без цієї евристики, навіть якщо система така, що на кожній i-ої фазі a_ii ≠ 0 — алгоритм Гауса-Жордана відпрацює, але в підсумку накопичується похибка може виявитися настільки величезною, що навіть для матриць розміру близько 20 похибка буде перевершувати саму відповідь.

Вироджені випадки

Отже, якщо зупинятися на алгоритмі Гаусса-Жордана з partial pivoting, то, затверджується, якщо m=n і система невирождена (тобто має ненульовий визначник, що означає, що вона має єдине рішення), то описаний вище алгоритм повністю відпрацює і прийде до одиничної матриці A (доказ цього, тобто того, що ненульовий опорний елемент завжди буде знаходитися, тут не наводиться).

Розглянемо тепер загальний випадок — коли n і m не обов'язково дорівнюють. Припустимо, що опорний елемент на i-му кроці не знайшовся. Це означає, що в i-му стовпці всі рядки, починаючи з поточної, містять нулі. Стверджується, що в цьому випадку ця i-ий змінна не може бути визначена, і є незалежною змінною (може приймати довільне значення). Щоб алгоритм Гауса-Жордана продовжив свою роботу для всіх наступних змінних, в такій ситуації треба просто пропустити поточний i-ий стовпець, не збільшуючи при цьому номер поточного рядка (можна сказати, що ми віртуально видаляємо i-й стовпець матриці).

Отже, деякі змінні в процесі роботи алгоритму можуть надаватися незалежними. Зрозуміло, що коли кількість m змінних більше кількості n рівнянь, то як мінімум m-n змінних виявляться незалежними.

В цілому, якщо знайшлася хоча б одна незалежна змінна, то вона може приймати довільне значення, в той час як інші (залежні) змінні будуть виражатися через неї. Це означає, що, коли ми працюємо в полі дійсних чисел, система потенційно має нескінченно багато рішень (якщо ми розглядаємо СЛАР за модулем, то число рішень буде одно цього модулю в ступені кількості незалежних змінних). Втім, слід бути обережним: треба пам'ятати про те, що навіть якщо були виявлені незалежні змінні, тим не менш СЛАР може не мати рішень взагалі. Це відбувається, коли залишилися необробленими рівняннях (тих, до яких алгоритм Гауса-Жордана не дійшов, тобто це рівняння, в яких залишилися тільки незалежні змінні) є хоча б один ненульовий вільний член.

Втім, простіше це перевірити явною підстановкою знайденого рішення: всім незалежними змінними присвоїти нульові значення, залежною змінною присвоїти знайдені значення, і підставити це рішення в поточну СЛАР.