В.А. Ильин, Э.Г. Позняк - Линейная алгебра (6-е издание) (1113061), страница 34
Текст из файла (страница 34)
Итерационные методы весьма удобны для использования современной вычислительной техники. Изложению наиболее употребительных итерационных методов решения линейных систем посвящен 9 1 настоящей главы. Итерационные методы находят широкое применение и при решении другой важной вычислительной задачи линейной алгебры — так называемой полной проблемы собственных значений (так называют проблему отыскания всех собственных значений и отвечающих им собственных векторов заданной матрицы з)). В итерационных методах собственные значения вычисляются как пределы некоторых числовых последовательностей без предварительного определения коэффициентов характеристического многочлена. ') Практически метод, основанный на формулах Крамера, обычно не применяется, ибо он требует проведения очень большого числа арифметических операций и записей. Более удобным является точный метод, основанный на последовательном исключении неизвестных и называемый методом Гаусса )его изложение можно найти, например, в книге Фаддеев Д.
К., Фаддеева В. Н. Вычислительные методы линейной алгебры. — Мл Физматгиз, )963, гл. 2) ) В отличие от этой проблемы, задачу отыскания некоторых (например, наибольших по модулю) собственных значений заданной матрицы называют частичной проблемой собственных значений. !55 МЕТОДЫ РЕШЕНИЯ ЛИНЕИНЫХ СИСТЕМ В 32 настоящей главы разбирается один из самых важных (наиболее употребительных на ЭВМ) итерационных методов решений полной проблемы собственных значений так называемый метод враи1ений (или метод Якоби). Этот метод применим ко всякой симметричной (или к эрмитовой) матрице, легко реализуется на ЭВМ и всегда сходится. Он устойчив по отношению к ошибкам округления результатов промежуточных вычислений и обладает тем замечательным свойством, что наличие кратных и близких друг к другу собственных значений не только не замедляет его сходимости, а напротив, ускоряет ее.
Метод вращений, предложенный Якоби и известный еще с середины прошлого века, долгое время не находил практического применения из-за большого обьема вычислений, необходимых для его реализации. И лишь появление быстродействующих электронных вычислительных машин сделало его самым эффективным методом решения полной проблемы собственных значений симметричных и эрмитовых матриц. ф 1.
Итерационные методы решения линейных систем 1. Метод простой итерации (метод Якоби). Рассмотрим квадратную систему линейных уравнений с вещественными коэффициентами (3.10) (см. и. 1 З2 гл.3), которую запишем в матричном виде (6.1) понимая под А основную матрицу системы он а|г ... вы агг агг ... аг„ (6.2) а~ а„г ... а„„ Ж! У~ а под Х и г векторы-столбцы вида Х =, г' = г, первый из Ж которых подлежит определению, а второй задан.
Предлагая однозначную разрешимость системы (6.1), заменим матричное уравнение (6.!) эквивалентным ему матричным уравнением Х = Х вЂ” ТАХ+ тг, в котором через т обозначено вещественное число, обычно называемое стационарным параметром. С помощью этого последнего уравнения составим итерационную последовательность векторов (Хь), определив ее рекуррентным соотношением Хьэ| = Хь — ТАХь + тг (и = О, 1, ...) (6.3) при произвольном выборе «нулевого» приближения Хо. Метод простой итерации заключается в замене точного решения Х системы (6.!) й-й итерацией Хь с достаточно большим номером и.
Оценим погреганость ль = Хь — Х метода простой итерации. 156 ИТЕРАЦИОННЫЕ МЕТОДЫ РЕШЕНИЯ ЛИНЕИНЫХ СИСТЕМ (гл. 6 Из соотношений (6.3) и (6.1) сразу же вытекает следующее матричное уравнение для погрешности Уьл Уя,.1 = (Š— ТА)Уь, (6.4) где Š— единичная матрица порядка п. Введем в рассмотрение норму вектора в пространстве Е" и операторную норму квадратной матрицы порядка п. Как обычно, назовем нормой вектора Х число ~~Х~~, равное корню квадратному из суммы квадратов координат этого вектора.
Назовем операторной нормой произвольной матрицы А число ~~А~~, равное либо точной верхней грани отношения ()АХ)(/!)Х)( на множестве всех ненулевых векторов Х, либо (что то же самое) точной верхней грани норм )(АХ)! на множестве всех векторов Х, имеющих норму, равную единице. Итак, по определению )АХ! ~~А~~ = "'р ~~х~~ (6.5) (6,8) ') Матрица А называется симметричной, если А = А'. Напомним, что для любой симметричной матрицы А ') операторная норма этой матрицы равна наибольшему по модулю собственному значению этой матрицы (см.
и. 4 35 гл. 5), т.е. )(А(( = гпах )Л,(. (6.6) Из (6.5) вытекает следующее неравенство, справедливое для любой матрицы А и любого вектора Х: )(АХ)( < !)А() )(Х)!. (6.7) Из матричного уравнения для погрешности (6.4) и из неравенства (6.7) мы получим, что для любого номера й РФ,1~! < 1~Š— тАй !~У,~~. Докажем теперь следующую простую, но важную теорему. Теорема 6.1. Для того чтобы итерационная последовательность (6.3) при любом выборе нулевого приближения Хо и при данном значении параметра т сходилась к точному решению Х системы (6.1), достаточно, чтобы было выполнено условие р = ))Š— ТА~~ < !.
(6.9) При этом последовательность (6.3) сходится со скоростью геометрической прогрессии со знаменателем р. В случае, если матрица А является симметричной, условие является и необходимым условием сходимости итерационной последовательности (6.3) при любом вгяборе нулевого приближения. Д о к а з а т е л ь с т в о. Для установления достаточности условия (6.9) заметим, что из неравенства (6.8) вытекает следующее соотношение: ях3ья < ЗŠ— ТА~я"' 'Зкоа.
(6.10) !57 МЕТОДЫ РЕШЕНИЯ ЛИНЕИНЫХ СИСТЕМ Из (6.10) очевидно, что условие (6.9) обеспечивает сходимость последовательности погрешностей 2ь к нулю со скоростью геометрической прогрессии со знаменателем р. В случае, если матрица А является симметричной, будет симметричной и матрица гр — ТА, а поэтому в силу (6.6) условие (6.9) можно переписать в эквивалентном виде (6.! 1) р = пзах (! — ТЛ„! < 1 (здесь через (Л,7 обозначены собственные значения матрицы А). Убедимся в том, что условие (6.11) является необходимым условием сходимости к нулю последовательности (ЯЕ7 при любом выборе нулевого приближения Хо.
Предположим, что условие (6.11) не выполнено. Тогда существует собственное значение Л„удовлетворяющее неравенству ~1 — ТЛ,~ > 1. Обозначим через Хбй отвечающий этому собственному значению собственный вектор матрицы А и выберем нулевое приближение Хо так, чтобы Яо совпало с Х('1. Тогда, последовательно записывая соотношение (6А) для номеров 1, 2, ..., к, мы получим, что 2ь = (1 — ТЛ,)" Ео.
Из последнего соотношения в силу неравенства (! — ТЛ„( > 1 вытекает, что 5Яь)! не стремится к нулю при к -э сю. Теорема 6.1 доказана. Сразу же заметим, что для практических целей недостаточно установить только факт сходимости последовательности итераций. Центральной задачей численных методов является оценка скорости сходимости. Очень важно знать, как наилучшим способом распорядиться стационарным параметром т для того, чтобы получить наиболее быструю сходимость. Остановимся на этом вопросе подробнее.
Пусть задана е-точность, с которой нам требуется получить точное решение системы (6.!). Требуется найти итерацию Хя с таким номером й, для которого (6.12) Из (6.9) и (6.10) вытекает, что /!Еь/! < р" !!Уо/! и, стало быть, (6.!2) выполняется при р" < е, т.е. при Й >!п(!Ге)7'!п(1/р). Отсюда видно, что для уменьшения числа итераций к, достаточных для достижения требуемой е-точности, следует выбрать параметр т так, чтобы получить минимум функции р = р(т) = ЕЯ вЂ” тА~Е.
Считая матрицу А симметричной и положительно определенной, мы приходим к следующей задаче оптимизации: найти минимум функции ппп р(т) = пнп (/Š— ТА$~ = тш(гпах (! — ТЛ,!). Решение этой и несколько более общей задачи, предложенное А.А. Самарским, излагается в следующем пункте. Там будет доказано, что указанный минимум функции р = р(т) достигается для значения т = 27(т1 + тз), где ъ и та — соответственно минимальное и максимальное собственные значения матрицы А, причем минимальное 158 ИТЕРАЦИОННЫЕ МЕТОДЫ РЕШЕНИЯ ЛИНЕИНЫХ СИСТЕМ (гл. 6 значение функции р(т) равно 1 7~ 77« ти 71 1+ 7~ 7'7« Т + 71 2. Общий неявный метод простой итерации. Снова обратимся к решению линейной системы (6.1), но на этот раз заменим итерационную последовательность (6.3) более общей итерационной последовательностью, определяемой соотношением (6.!3) т в котором В представляет собой некоторую «легко обратимую» квадратную матрицу а-го порядка, а т — стационарный параметр.
Такой метод составления итерационной последовательности и называется неявным методом простой итерации. Рассмотренный в предыдуцьем пункте явный метод простой итерации получается из неявного метода в частном случае В = В, где  — единичная матрица порядка а. Для того чтобы сформулировать в удобной для приложений форме условие сходимости общего неявного метода простой итерации, напомним некоторые понятия, введенные в предыдущей главе. Напомним, что матрица А называется положительно определенной, если (АХ, Х) > 0 для любого ненулевого вектора Х. В гл. 5 было доказано, что необходимым и достаточным условием положительной определенности симметричной матрицы А (или, что то же самое, самосопряженного линейного оператора А) является положительность всех собственных значений этой матрицы (этого оператора). Если матрица А является аоложительно определенной, то мья договоримся писать неравенство А > О.
Далее договоримся писать неравенство В > А (или А < В) в случае, если  — А > 0 (т.е. если матрица  — А является положительно определенной). Докажем следующую замечательную теорему ') . Теорема 6.2 (теорема А.А. Самарского). Пусть матрица А является симметричной и вьшолнены условия А > О, В > 0 (симметричность матрицы В, вообще говоря, не предполагается). Тогда для того чтобы итерационная последовательность, определяемая соотношением (6.!3) ари любом выборе нулевого приближения Хо сходилась к точному решению Х системы АХ = Р', достаточно, чтобы были выполнены условия (6.!4) 2В>тА, тА>0 При дополнительном предаоложении о том, что матрица В является симметричной, условия (6.14) не только достаточны, но ') Эта теорема является частным случаем доказанного известным советским математиком А.А.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
