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