Метод ортогонализации решения систем с произвольной невырожденной матрицей

17.Метод ортогонализации

Этот метод используется для решения систем с произвольной невырожденной матрицей, но по скорости уступает многим прямым методам примерно в 1,5-3 раза. Метод основан на построении вспомогательной системы векторов, связанных с матрицей исходной системы уравнений и ортогональные в некоторой метрике.

Рассмотрим систему (4.1) и запишем ее в виде

, (4.19) где , . Обозначим , , . Тогда система (4.19) перепишется в виде

 Решение системы уравнений с невырожденной матрицей А сводится к нахождению такого вектора y, который имеет последнюю координату, равную единице, и ортогонален к линейно независимым векторам a₁,a₂,…,a_n. Ортогональность вектора y к векторам a₁,a₂,…,a_n влечет за собой ортогональность ко всему подпространству , натянутому на них, и, следовательно, к любому его базису. И наоборот, ортогональность вектора y к некоторому базису подпространства P_n влечет ортогональность ко всем векторам a_i. Поэтому для решения системы достаточно построить ненулевой вектор , ортогональный к какому-нибудь базису подпространства . Если  - последняя координата вектора , то .

Добавим к  системе векторов a₁,a₂,…,a_n линейно независимый с ними вектор , а затем будем последовательно строить систему ортонормированных векторов b₁,b₂,…,b_n+1, что для всех  векторы b₁,b₂,…,b_k являются базисом подпространства , натянутого на вектора a₁,a₂,…,a_k. В этом случае вектор  и будет искомым вектором . Применим правило Шмидта для построения ортонормированного базиса пространства, натянутого на заданные линейно независимые векторы. Обозначим через u₁,u₂,…,u_k ортогональный базис подпространства , а через b₁,b₂,…,b_k - ортонормированный в евклидовой метрике базис того же подпространства. Так как векторы  нормированы, то их можно представить в виде ,       .(4.20) На первом шаге метода положим , . Пусть для некоторого шага  уже построен ортогональный базис u₁,u₂,…,u_k и ортонормированный базис b₁,b₂,…,b_k подпространства . Вектор  будем искать как линейную комбинацию векторов

Условие ортогональности вектора  к ортогональным векторам u₁,u₂,…,u_k  или, что то же самое, к векторам b₁,b₂,…,b_k дает . Поэтому . (4.21) Таким образом, с помощью этого итерационного процесса и соотношения (4.20) строится ортонормированная система векторов b₁,b₂,…,b_n+1. Векторы b₁,b₂,…,b_n являются базисом подпространства . Следовательно, решение исходной системы имеет вид , , где  и  - соответственно -я и я

координаты вектора . Метод ортогонализации легко реализуется на ЭВМ и для решения системы  уравнений требует  операций умножения и деления и  извлечений квадратного корня. Однако удовлетворительные по точности результаты этот метод дает не для всех матриц A.Это связано с неустойчивостью рекуррентного процесса (2.21), нарушающей ортогональность векторов b₁,b₂,…,b_n+1. Чтобы избежать этого недостатка используется алгоритм Уилкинсона. В соответствии с этим алгоритмом векторы  вычисляются из соотношения , где , .  При  метод ортогонализации принимает обычный вид и может быть неустойчивым. Значительно лучшие результаты дает . Обычно же для достижения хорошей точности достаточно сделать две-три итерации.