Беклемишев - Дополнительные главы линейной алгебры (947281), страница 36
Текст из файла (страница 36)
Матрица г называется эквивалентным возмущением для А, а столбец у — для Ь. Нормы эквивалентных возмущений являются характеристикой точности решения. Невязку вычислить удобнее, так как точное решение ха нам неизвестно, но интересует нас главным ооразом погрешность. Из очевидного равенства Абх=Ь вЂ” Ах=г (14) следует )бх) )Л-') ) ). Поэтому из малости 1!г1~ вытекает, что 1~бх1~ мала.
Но если А ' имеет большую норму, то нужно добиться очень малой невязки, для того чтобы иметь гарантированно малую погрешность. Возможен следук>щий подход. Если невязка г вычислена с повышенной точностью (с использованием режима накопления), то вычисленное решение бх системы (14) служит хорошей оценкой для бх. 1(роме того, х,= х+ бх есть лучшее приближение к истинному решению, чем х. Вычисляя невязку, которую дает х„ можно получить следующее приближение х,, и т. д. Подробнее мы ошппем этот процесс в следующем парагра>(е, но сейчас следовало упомянуть о нем, так как по скорости сходимости последовательности х, х„х,„... можно судить об обусловленности матрицы А.
Соответствующая оценка будет получена на стр. 167. Вычисление последовательных прибльпкеннй не связано с большим увеличением числа операций и времени счета, так как при решении систем вида (14) используется уже полученное разложение матрицы Л на множители (1Л/- или 1,>)т-разложение). Поэтому иногда считается целесообразным (см. Уилкинсоц и Райнш 1341) использовать построение последовательных приближений, вместо того чтобы находить число обусловленности и с его помощью оценивать точность решения. Перейдем теперь к оценке относительной погрешности. Здесь нам придется ограничиться только формулировками.
Если 1 (>'-разложение получено методом Гаусса с выбором главного элемента по столбцу, то произведение 7.(>' в точности удовлетворяет равенству Ш= А+а, причем )6)в ( лРи)А)в. (15) Здесь и — единичная ошибка округления, зависящая от точности применяемой вычислительной системы, а р определяется так> гл пь введение в численные методы если а<'> — элементы матриц А~"', которые вычисляются в процессе исключения, то р — йпах ~а~".>~1( А )е'. 21 „! Таким образом, р может быть определено только после окончания вычислений. В этом смысле оценка является апостгриорной. Она может быть использована как априорная оценка, если учесть следующее соображение, основанное на опыте вгячисленнй: если матрица пе является плохо обусловленной, то гпах ~а~,"Д ~ превосходит ьпх шах ~ ам ( не больше чем в несколько раз.
ь~ Оказывается, что мы можем записать эквивалентное возмущение для других встречавшихся нам разложений на множители в форме„аналогичной (15): полученное произведение матриц отличается от А на матрицу б, оцениваемую неравенством * )О).=--П ) (А)., (1б) где функция ) (и) зависит от порядка матрицы А и примененного алгоритма разложения.
Для ЛУ-разложения, получаемого по компактной схеме метода Гаусса, главный относительно и член функции )' представляет собой константу р', ио константа эта зависит от роста элементов матриц А во подобно определенной выше константе р. Это утвери;депне справедливо при условии, что вычисления по компактной схеме производятся в режиме накопления, и показывает, что в этом случае можно ожидать примерно и-кратного увеличения точности по сравнению с обычной схемой. Заметим, что для компактной схемы, применяемой к положительно определенной матрице, р' = 1. Существенное достоинство методов получения (Я-разложения в том, что для них ) (и) может быть априорно оценена.
Именно, как для метода вращения, так и для метода отражений главный член 1 (и) имеет вид 2,9п. (При этом для метода отражений, как было отмечено, обязательно применение режима накопления.) Далее, может быть показано, что для всех обсуждаемых методов относительная погрешность вычисленного решения удовлетворяет оценке )хО «(е о «2се(А)д(п)и 1 ~0 Ь где главные относительно и члены функций и и ) совпадают.
й 4. Итерационные методы решения систем линейных уравнений 1. Введение. Изложенные в 2 3 прямые методы решения систем линейных уравнений теоретически приводят к точному решению. Сейчас мы займемся итерационными методами, с помощью которых З 4, ИТЕРАЦИОННЫЕ МЕТОДЫ РЕШЕНИЯ СИСТЕМ 161 в принципе может быть построено не решение, а только последовательность, к нему сходящаяся. Некоторый достаточно близкий к пределу член этой последовательности принимается за приближенное решение. Таким образом, итерационные методы имеют некоторую теоретически необходимую ошибку.
Это ни в коем случае не является их недостатком по сравнению с прямыми методами. Действительно, упомянутая ошибка может быть сделана меньше, чем погрешность, вызванная ошибками округления при получении решения прямым методом. Как мы увидим ниже, в п, 3, итерационные методы могут применяться для уточнения решений, найденных при помощи прямых методов. Слабость итерационных методов в том, что каждый из них сходится, т. е.
дает сходящуюся последовательность, вообще говоря, не для любой системы линейных уравнений. Однако для какого-либо выбранного метода часто возможно так преобразовать систему, чтобы для преобразованной системы этот метод сходился. Эффективность итерационного метода во многом определяется скоростью его сходимости, и потому скорость сходимости всегда находится в центре внимания при разработке таких методов.
Характерно также, что итерационные методы работают лучше, если известно хорошее начальное приближение, принимаемое за первый член последовательности, хотя обычно они сходятся при любом начальном приолижении. Конечно сходимость итерационных методов может иметь место только теоретически.
В силу неизбежных ошибок округления вычисленные приблихкения несколько отличаются от истинных. Поэтому нельзя утверждать, что вычисленные приближения с достаточно большими номерами лежат в сколь угодно малой окрестности истинного ре~нения. Можно сказать только, что они попадают в некоторую его окрестность, размеры которой определяются точностью вычисчений. После того как получено приближение из этой окрестности, дальнейшие вычисления нв повышают точности результата.
Типичная область применения итерационных методов — зто системы линейных уравнений, возникающие при численном решении уравнений с частными производными. Обычно это системы из большого числа уравнений с большим числом неизвестных, матрицы которых могут легко записываться и обрабатываться только благодаря их специальному строению. Но специальное строение матриц, как правило, нарушается прн тех преобразованиях, которым оии подвергаются при применении прямых методов. Итерационные методы свободны от этого недостатка.
Большое количество итерационных методов (и не только для систем линейных уравнений) может быть получено применением принципа неподвижной точки (иначе называемого принципом сжатых отображений). Приведем его формулировку. Пусть Π— полное линейное нормированное пространство и Р— его отображение (не обязательно линейное) в себя. Г назы- 162 гл, нь вввдвнив в числвнныв матоды вается сжимающим множество гь" с= .о, если существует такое число а ы [О, 1), что для любых х' и х" из ль выполнено условие (,Г(х') — г (х')((сг)х' — х" (.
Заметим, что определение зто применимо и тогда, когда Г определено не на всем пространстве Х, а только на множестве .Ф. Т е о р е м а 1, Пусть .ГС вЂ” захчкнутое ограни мнное множество в Ж и отображение г сжимает х. Тогда уравнение х=Е(х) (1) ил1еет в С одно и только одно решение. Поскольку иам не придезся использовать зту общую формулировку, мы не приводим доказательства, которое можно найти, например, в книге Федорюка (Зб). Доказательство основано иа том, чго в условиях теоремы любая последовательность векторов (хг) пз х, задаваемая рекуррентной формулой хь,, = г" (хг), (2) сходится к решению уравнения (1). 2. Метод простой итерации.
Проще всего придать системе линейных уравнений Ах= о вид (1), прибавив х к обеим частям равенства. х=х — Ах+Ь=(Š— А)х+Ь, Волее общую формулу мы получим, если предварительно умножим обе части равенства па невырожденную матрицу Н х = х + Н (й — Ах). Зто позволяет построить итерационный процесс, задаваемый ре. куррентиой формулой хгег = хь+ Л (б — Ахь).
(3) Введя параметр т и обозначив Н через тВ ', мы можем перепиаать формулу (3) в виде Вхьц — хд+ 1 (4) Нахождение приближенного решения о использованием формулы (3) называется методом простой итерации или спгацвонарным методом. Формула (4) соответствует оби(елгу неявному методу простой итерации. Значение параметра т выбирается для конкретной системы так, чтобы скорость сходимости была максимальной. Формулам (3) и (4) можно придать вид хьез —— Рхь+Т, (3) если положить Р = Š— НА, а Т НЬ, или соответственно Р ь = Š— тВ 'А и Т = тВ Ч>. ГЛ.
Н!. ВВЕДЕНИЕ В ЧИСЛЕННЫЕ МЕТОДЫ где Я!! — компонентные матрицы для матрицы Р, число различных характеристических чисел обозначено через з, а кратность »-го числа — через т!. Отсюда в силу линейной независимости компонентных матриц непосредственно вытекает доказываемое. 3 а м е ч а н н е. Из доказательства предложения 1 видно также, что итерационный процесс сходится тем быстрее, чем меньше спектральный радиус матрицы Р. П р едл о ж е н и е 2. Если ~| Р 1! «1, то рекуррентнаТ! последовательность, задаваемая формулой (5), при любол! начальном в!кторе сходится не медленнее, чел! сйл!ма геояеп»рической прогрессии со знаяенателем !! Р !!. То, что условие 1! Р ~~ «1 достаточно для сходимости рассматриваемой последовательности, непосредственно вытекает из предложения 1, если вспомнить оценку для спектрального радиуса матрицы (предложение 1 ~ 4 гл.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
