Самарский А.А., Гулин А.В. Численные методы (1989) (1095856), страница 17
Текст из файла (страница 17)
Из неравенства С)0 следует, что существует константа б)0 такая, что (Сх, х) >б!1х))в. Действительно, если С>0 — симметричная матрица, то все ее собственные значения положительны и в качестве 6 можно взять минимальное собственное значение. Если С)0 — несимметричная матрица, то для любого хе=Н, хчьО имеем (Сх, х) = — [(Сх, х) + (х, С'х)1 ) О, где С' — матрица, транспонированная к С. Поэтому в качестве б можно взять минимальное собственное значение матрицы С,= =0,5(С+С'). Из оценки (Сх, х) >б!!х!!в следует, что существует матрица С-'. Неравенство С>0 означает, что (Сх, х) )О для всех хепН. Если С>0, то С-' может и не существовать. 88 где х, задан.
Говорят, что итерационный метод (2) сходится, если )!х„— х~~-ь -+-0 при и — со. Под нормой вектора х будем понимать сейчас среднеквадратичную норму Перейдем к исследованию сходимости итерационного метода (2). Погрешность метода на пяй итерации характеризуется вектором г„=х„— х, который согласно (1), (2) удовлетворяет однородному уравнению В "" " +Аг„=О, п=О, 1, ..., г =х,— х. (3) Теорема 1. Пусть А — симметричная положительно определенная матрица, т)0 и пусть выполнено неравенство  — 0,5тА ) О.
(4) Тогда итерационныи метод (2) сходится. Доказательство. Достаточно показать, что среднеквадратичная норма решения г„уравнения (3) стремится к нулю при и — «оо и при любой начальной погрешности г,. Покажем сначала, что при условии (4) числовая последовательность Х„= (Аг„, г„) является невозрастающей. Из уравнения (3) найдем г„+,= (Š— тВ-'А)г„, Аг„,= (А — тАВ-'А)г„, откуда получим (Аг„~ь г„~,) = (Аг„, г„) — т (АВ-'Аг„, г„)— — с(Аг„, В-'Аг.)+т'(А В 'Аг„, АВ-'Аг„). Вследствие симметричности матрицы А имеем (АВ-'Аг„, г„) = (Аг„, В-'Аг„), поэтому (Аг„„г„,,) = (Аг„, г„) — 2т(( — 0,5тА) В-'Аг„, В 'Аг„). Отсюда, учитывая условие (4), получаем неравенство (Аг„„, г„„) ( (Аг„, г„) .
(5) Таким образом, числовая последовательность л'„= (Аг„, г„) монотонна и ограничена снизу нулем. Следовательно, существует 1пп л„=л. (б) где ю„=В-'Аг . Наконец, замечая, что А — положительно опреде вт Далее, из положительной определенности матрицы  — 0,5тА следует существование константы б) 0 такой, что Ц — 0,5тА)В 'Аг„, В 'Аг„))Я1В 'АгД'. Отсюда и из (5) получаем неравенство У„+,— У„+26т!! В 'Аг„~Р(0.
Переходя в этом неравенстве к пределу при и- оь и учитывая (б), убеждаемся в том, что существует 1нп ~ш„~=О, ленная и, следовательно, обратимая матрица, получим г„=А-'Вге„, !!г„!!(!(А-'В(!!!и„!! и тем самым 1пп (!г„(! = О. а-Ф о Теорема 1 доказана. 3 а меча нне.
Как показано в (32, с. 627), нри условиях теоремы 1 для погрешности г„=л — л итерационного метода (2) справедлива оценка !!за!!л~а"!!зО!! л, где реа(0, 1), !!зь!л (Аа, з )ть Эта опенка означает, что метод сходится со скоростью геометрической прогрессии со знаменавелем р. Константа р (1 — 2тб.бВВ!а)", где б — минимальное собственное значение матрицы А и б, — минимальное собственное значение матрицы О,б (В*+ †). Применим теорему 1 к конкретным итерационным методам, рассмотренным в предыдущем параграфе. Метод Якоби имеет следующий канонический вид: 0(х„+,— х„)+Ах„=(, (7) где 0=г((ап (ась аао ..., а„„).
Таким образом, в данном случае В=0, т=1. С л е д с т в и е 1. Пусть А — симметричная положительно определенная матрица с диагональным преобладанием, т. е. асс),Я~ ~ац(, (=1,2, ..., пг. (8) гти Тогда метод Якоби сходится. Доказательство. Условие сходимости (4) в данном случае имеет вид А~20. Покажем, что это матричное неравенство следует из неравенств (8). Рассмотрим положительно определенную квадратичную форму (Ах, х) = ~ч(' ,апхгхт с/=г и воспользуемся оценками (Ах, х)( — ~ (ау(х', + — ~ (ац(хз(= 1 1 с)=т Ьг=з = — ~ !ац(х,'+ — 'Я !ап(х,'.
1 з 1 2 2 с/=ь ь! 1 Из условий симметричности и положительной определенности матрицы А имеем ам=аз, ао)0, 1, 1=1, 2, ..., т, и поэтому предыдущая оценка приводит к неравенству (Ах, х)( ~ )аи!х,'="Я х,'.ф (ац !+агг) . С!=г г=т ~!еч Перепишем условие (8) в виде аи +,Я ~ ау ~ ( 2аи, 1 = 1, 2, ..., гп. 1, -С Тогда из неравенства (9) получим (Ах, х)(2'Я аих,'=2(Рх, х), что и требовалось.
Следствие 2. Пусть А — симметричная положительно определенная матрица. Тогда метод верхней релаксации (Р+аА,) ' " +Ах,=1 сходится при условии 0<в<2. В частности, метод Зейделя (а=1) сходится. Д о к а з а т е л ь с т в о. Метод верхней релаксации приводится к каноническому виду (2) с В=Р+аАь к=в. Напомним, что исходная матрица А представляется в виде суммы А=Р+А,+А„где А,— нижняя треугольная, А,— верхняя треугольная и Р— диагональная матрицы (см. (7) из $ 1). Для симметричной матрицы А матрица А, является транспонированной к А„поэтому (Ах, х) = (Рх, х)+ (А,х, х)+ (А,х, х) = (Рх, х) +2 (А,х, х) . Условие сходимости (4) принимает внд (Вх, х) — О,бв(Ах, х) = ((Р+аА,)х, х) — Обо>((Рх, х)+2(А,х, х)) =(1 — 05а) (Рх, х)>0 и выполняется при 0<в<2.
Рассмотрим еще вопрос о сходимости метода простой итерации " +Ах,=Т с симметричной положительно определенной матрицей А. Согласно (4) метод сходится при условии Š— О,бтА >О. (11) Какие ограничения на параметр т накладывает условие (11)? Пусть Хь 1=1, 2, ..., т,— собственные значения матрицы А, расположенные в порядке возрастания. Условие (11) эквивалентно тому, что все собственные значения матрицы Š— 0,5тА положительны.
Достаточно потребовать положительности минимального собственного числа этой матрицы, равного 1 — 0,5тХ . Таким образом, итерационный метод (10) сходится, если т<2/Х „, (12) где Х вЂ” максимальное собственное число матрицы А. 89 Условие (12) и необходимо для сходимости метода (10), т. е. если (12) нарушено, то найдется начальное приближение х„при котором 11х — х11тьО при и — ~со. Докажем последнее утверждение. Возьмем в качестве начального приближения вектор х,=«+1«, где х — точное решение задачи (1), а р — собственный вектор матрицы А, отвечающий собственному числу Х „=Х„, т.
е. Ар=), 1«. Прн таком выборе начального приближения имеем г,=х,— х=1«. Из уравнения (3) при В=В получим = ( — тА) "г = (Я вЂ” тА) и, следовательно, г„=(! — тй ) "р, 11г„11= !1 — тй ! "11р11. Если т= 2Х ', то 11г„11=1!!«11-у 0 при л — оо. Если же т) 2Х ', то 11 — тЛ 1)! и !1г„!1-э-оо при п-~-оо. Таким образом, условие (12) необходимо и достаточно для сходимости метода простой итерации (10). В заключение параграфа отметим, что теория итерационных методов не заканчивается исследованием сходимости. При наличии хотя бы двух итерационных методов возникает вопрос о том, какой из этих методов сходится быстрее, т. е.
для какого метода погрешность !1х„— х11 станет меньше заданного числа е при меньшем числе итераций п. Сюда же примыкает вопрос о нахождении итерационных параметров, минимизирующих число итераций, необходимых для получения заданной точности. Этот круг вопросов будет подробно рассмотрен в следующих параграфах. $ 3. Необходимое и достаточное условие сходимости стационарных итерационных методов 1. Введение. Некоторые итерационные методы решения систем линейных алгебраических уравнений уже рассматривались в 5 1, 2. Напомним необходимые для дальнейшего сведения.
Пусть дана система уравнений Ах=~, (1) где А= !ач), 1, /=1, 2,..., т,— вещественная квадратная матрица, имеющая обратную, и х= (х„х„..., х )', ) = (1„)ь..., ) )'. Канонической формой одношагового итерационного метода называется его запись в виде «««1 «« В„„+ Ах„= ~, л = О, 1, ..., (2) «+1 где п — номер итерации, х, — заданное начальное приближение, «Ю «т х„= (х„х„..., х ) .
Матрицы В„.„и числа т.+,)О задают тот или иной конкретный итерационный метод. В настоящем параграфе подробно рассматриваются стационарные итерационные методы (3) в которых матрица В н числовой параметр т не зависят от номера итерации и. Погрешность итерационного метода (3) о„=х„— х, где х— ное решение системы (1), удовлетворяет уравнению В "" "+Ао„=О, п=О, 1, ..., о,=х,— х, (4) которое отличается от уравнения (3) лишь тем, что является однородным. Сходнмость итерационного метода (3) означает, что о„-+.О в некоторой норме при и-+-оо. Переписывая уравнение (4) в разрешен. ной относительно о„+, форме о»+1 Во» (б) где (б) З=Š— тВ 'А, видим, что свойство сходимости итерационного метода целиком определяется матрицей 5.
Необходимые н достаточные условия сходимости в терминах матрицы 5 приведены ниже в п. 3. Матрица В называется л/атрицей перехода от п-й итерации к (п+1)-й. 2. Норма матрицы. При исследовании сходимости будем рассматривать векторы х„и х как элементы пт-мерного линейного пространства Н, в котором введена норма 11х~~ вектора х. Нормой матрицы А, подчиненной данной норме вектора, называется число '1А1= зпр 1( — "-~- . »~о 1!л11 Норму вектора в пространстве Н можно ввести различным образом.
Нам прежде всего потребуется норма ~х~~с= шах ~х;~. тиЩВ Подчиненная ей норма матрицы А выражается через элементы матрицы А следующим образом: т $А~с= шах 'Я1а//1 тж/ж»а . /ао Докажем ато утверждение. Для любого вектора х справеллнво неравенство 1Ал1 = нтах ~~~~ а/х/ ~ тах 1х/1 н/ак ~ч~~ ~)а/;1= 1я/кои 1м/жш тм/~п$ /вм /=т гоак Я 1а//1 11х1 1 1~/же в. е. ~» 1Ал1с( юах Я 1а,/1 1л~.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
