Ильин, Позняк - Линейная алгебра (947283), страница 34
Текст из файла (страница 34)
В итерационных методах соб- «) Практически метод, основанный на формулах Крамера, обычно не прн. меняется, ибо он требует проведения очень большого числа арифметических операций н записей. Более удобным является точный метод, основанный на по. следовательном исключении неизвестных и называемый м е т о д о и Г а у с с а (его изложение можно найти, например, в книге Д. К. Фаддеева и В.
Н. Фаддеевой «Вычислительные методы линейной алгебры», Гостехнэдат, )963, гл. 2). '«) В отличие от этой проблемы. задачу отыскания иекоторйх (например, наибольших по модулю) собственных значений заданной матрицы наэываот частичной проблемой собственных значений. а |! НтеРАционные методы Решения линейных систем !з! ственные значения вычисляются как пределы некоторых числовых последовательностей без предварительного определения коэффициентов характеристического многочлена. В $ 2 настоящей главы разбирается один из самых важных и наиболее употребительных на ЭВМ итерационных методов решения полной проблемы собственных значений — так называемый метод вращений (или метод Якоби).Этот метод применим ко всякой симметричной (или к эрмитовой) матрице, легко реализуется на ЭВМ и всегда сходится. Он устойчив по отношению к ошибкам округления результатов промежуточных вычислений и обладает тем замечательным свойством, что наличие кратных и близких друг к другу собственных значений не только не замедляет его сходимости, а, напротив, ускоряет ее.
Метод вращений, предложенный Якоби и известный еще с середины прошлого века, долгое время ие находил практического применения из-за большого объема вычислений, необходимых для его реализации. И лишь появление быстродействующих электронных вычислительных машин сделало его самым эффективным методом решения полной проблемы собственных значений симметричных и эрмитовых матриц. й 1. Итерационные методы решения линейных систем 1. Метод простой итерации (метод Якоби). Рассмотрим квадратную систему линейных уравнений с вещественными коэффициентами (3.!О) (см.
и. ! э" 2 гл. 3), которую запишем в матричном виде АХ =Р, (6.1) понимая под А основную матрицу системы ан а|4 ° ° ° а|л а94 ам ... аы (6.2) $ ал| алз ° ° ° алл Х| «4 а под Х и Р векторы-столбцы вида Х= , пер- ал зый из которых подлежит определению, а второй задан. Предполагая однозначную разрешимость системы (6.1), заменим матричное уравнение (6.1) эквивалентным ему матричным уравнением Х = Х вЂ” ТАХ + ТР, в котором через ч обозначено вещественное число, обычно называемое с т а ц и о н а р н ы м а а р а м е т р о м. |Зал 459 ~гл. е нтеэхпионнын методы 1а2 С помощью этого последнего уравнения составим итерационную последовательность векторов «Ха», определив ее рекуррентиым соотношением Ха д — — Ха — тАХа + тр (й = О, 1, ...) (6.3) прн произвольном выборе «нулевогоз приближения Х,.
Метод простой итерации заключается в замене точного решения Х системы (6.1) й.й итерацией Х, с достаточно большим номером й. Оценим ног р еш ность Ла = Մ— Х метода простой итерации. Из соотношений (6.3) и (6.1) сразу же вытекаег следующее матричное уравнение для погрешности Ед. Ха+ д —— (Š— тА) 2а, (6.4) где Š— единичная матрица порядка л. Введем в рассмотрение норму вектора в пространстве Е" и операторную норму квадратной матрицы порядка и. Как обычно, назовем н о р м о й в е к т о р а Х число 1Х~, равное корню хвадратному из суммы квадратов координат этого вектора.
Назовем операторной нормой произвольиойматрицы А число 1А1, равное либо точной верхней грани отношения '1АХ(д(Х(! нз множестве всех ненулевых векторов Х, либо (что то же самое) точной верхней грани норм)АХ( на множестве всех векторов Х, имеющих норму, равную единице. Итак, по определению )1А1= знр —. 1АХ( ХФО ЦХ1' (6.5) Напомним, что для любой симметричной матрицы Ае) операторная норма втой матрицы равна наибольшему по модулю собственному значению этой матрицы (см. и.
4 $ 5 гл. 5), т. е. (А/!= шах!Л,~. (6.6) Из (6.5) вытекаег следуюшее неравенство, справедливое для любой матрицы А и любого вектора Х: (~АХ1~ '1А~)Х1. (6.7) Из матричного уравнения для погрешности (6.4) и из неравенства (6.7) мы получим, что для любого номера й ~Я~„~ ч. 1 "Š— тА11хэ 1. (6.8) Докажем теперь следующую простую, но важную теорему. ') Матрица А называется с и и и е т р а ч н о й, есан А = А'. итерационные методы вешания линейных систем Теорема б.1. Для того чтобы итерационная последовательность (6.3) при любом выборе нулевого приближения Х, и при данном значении параметра т сходилась к точному решению Х системы (6,1), достаточно, чтобы было выполнено условие р=»»Е — тА)»(1, (6.9) При этом последовательность (6.3) сходится со скоростью геометрической прогресси и со знаменателем р.
В случае„если матрица А является симметричной, условие (6.9) является и необходимым условием сходимости итерационной последовательности (6.3) при любом выборе нулевого приближения Хо. Д о к а з а т е л ь с т в о. Для установления достаточности условия (6.9) заметим, что из неравенства (6.8) вытекает следующее соотношение: »)Ео»» ~ »»Е — тА»о»Яо»». (6.10) Из (6.10) очевидно, что условие (6.9) обеспечивает сходнмость последовательности погрешностей Л„к нулю со скоростью геометрической прогрессии со знаменателем р.
В случае, если матрица А является симметричной, будет симметричной и матрица Š— тА, а поэтому в силу (6.6) условие (6.9) можно переписать в эквивалентном виде р=шах»1 — тк,» -1 (6.11) (здесь через [Х,» обозначены собственные значения матрицы А). Убедимся в том, что условие (6.1Ц является необходимым условием сходимости к нулю последовательности»г.д» при любом выборе нулевого приближения Х,.
Предположим, что условие (6.!1) не выполнено. Тогда существует собственное значение к„ удовлетворяющее неравенству»1 — т);» ~ 1. Обозначим через Хи> отвечающий этому собственному значению собственный вектор матрицы А и выберем нулевое приближение Х, так, чтобы Ео совпало с Хы>.
Тогда„последовательно записывая соотношение (6А) для номеров 1, 2, ..., я, мы получим, что Ео = = (1 — т).,)ойдо. Из последнего соотношения в силу неравенства » 1 — тло» ~ 1 вытекает, что»Д»» не стремится к нулю при й -о. оь. еорема 6.1 доказана. Сразу же заметим, что для практических целей недостаточно установить только факт сходимости последовательности итераций. Центральной задачей численных методов является оценка скорости сходнмости. Очень важно знать, как наилучшим способом распорядиться стационарным параметром ч для того, чтобы получить наиболее быструю сходимость.
Остановимся на этом вопросе подробнее. <гл. з итарационныа матоды !б4 Пусть задана е-точность, с которой нам требуется получить точное решение системы (6.1). Требуется найти итерацию Хь с таким номером й, для которого )сьЦ < а))се(. (6.12) Из (6.9) и (6.10) вытекает, что )2„) ~ р"))2е)!, н, стало быть, (6.12) выполняется при р" ~ а, т. е. при й~ — * !и ()/е) )и ()/р) * Отсюда видно, что для уменьшения числа итераций й, достаточных для достижения требуемой е-точности, следует выбрать параметр т так, чтобы получить минимум функции р = р(т) = = "),Š— тА). Считая матрицу А симметричной и положительно определенной, мы приходим к следующей задаче оптимизации: найти минимум функции ппп р (т) = пни )Š— тА ) = ш)п (и!ах ) 1 — тХ, )). Решение этой и несколько более общей задачи, предложенное А.
А. Самарским, излагается в следующем пункте. Там будет доказано, что указанный минимум функции р р (т) достигается для значения т 2/(у, + у,), где у, и Те — соответственно минимальное и максимальное собственные значения матрицы А, причем минимальное значение функции р (т) равно ! —— те те Ъ вЂ” те уз+ те Уе 2, Общий неявный метод простой итерации. Снова обратимся к решению линейной системы (6.1), но на этот раз заменим итерационную последовательность (6.3) более общей итерационной последовательностью, определяемой соотношением (6,13) в котором В представляет собой некоторую «легко обратимую» квадратную матрицу л-го порядка, а т — стационарный параметр.
Такой метод составления итерационной последовательности и называется неявным методом простой итера- и и и . Рассмотренный в предыдущем пункте явный метод простой итерации получается нз неявного метода в частном случае В = = Е, где Š†единичн матрица порядка л. Для того чтобы сформулировать в удобной для приложений форме условие сходимости общего неявного метода простой итерации, напомним некоторые понятия, введенные в предыдущей главе. ф 1) итнв»циоинын мвтоды гашения линениых систем 1бб Напомним, что матрица А называется и оп о ж и тел ь н о о п р ед ел е н н о й, если (АХ, Х) >О для любого ненулевого вектора Х. В главе 6 было доказано, что необходимым н достаточным условием положительной определенности симметричной матрицы А (или, что то же самое, самосопряжеиного линейного оператора А) является положительность всех собственных значений этой матрицы (этого оператора).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
