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

Страницы работы

Содержание работы

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

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

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

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

 Решение системы уравнений с невырожденной матрицей А сводится к нахождению такого вектора y, который имеет последнюю координату, равную единице, и ортогонален к линейно независимым векторам a1,a2,…,an. Ортогональность вектора y к векторам a1,a2,…,an влечет за собой ортогональность ко всему подпространству , натянутому на них, и, следовательно, к любому его базису. И наоборот, ортогональность вектора y к некоторому базису подпространства Pn влечет ортогональность ко всем векторам ai. Поэтому для решения системы достаточно построить ненулевой вектор , ортогональный к какому-нибудь базису подпространства . Если  - последняя координата вектора , то .

Добавим к  системе векторов a1,a2,…,an линейно независимый с ними вектор , а затем будем последовательно строить систему ортонормированных векторов b1,b2,…,bn+1, что для всех  векторы b1,b2,…,bk являются базисом подпространства , натянутого на вектора a1,a2,…,ak. В этом случае вектор  и будет искомым вектором . Применим правило Шмидта для построения ортонормированного базиса пространства, натянутого на заданные линейно независимые векторы. Обозначим через u1,u2,…,uk ортогональный базис подпространства , а через b1,b2,…,bk - ортонормированный в евклидовой метрике базис того же подпространства. Так как векторы  нормированы, то их можно представить в виде ,       .(4.20) На первом шаге метода положим , . Пусть для некоторого шага  уже построен ортогональный базис u1,u2,…,uk и ортонормированный базис b1,b2,…,bk подпространства . Вектор  будем искать как линейную комбинацию векторов

Условие ортогональности вектора  к ортогональным векторам u1,u2,…,uk  или, что то же самое, к векторам b1,b2,…,bk дает . Поэтому . (4.21) Таким образом, с помощью этого итерационного процесса и соотношения (4.20) строится ортонормированная система векторов b1,b2,…,bn+1. Векторы b1,b2,…,bn являются базисом подпространства . Следовательно, решение исходной системы имеет вид , , где  и  - соответственно -я и я

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

Похожие материалы

Информация о работе