Фаддеев, Фаддеева - Вычислительные методы линейной алгебры (947503), страница 35
Текст из файла (страница 35)
За исходную матрицу 5о нужно взять, очевидно, 5о — — А — Г. Матрица 5„=5„равна А В табл. 1!.19 дано обращение матрицы по этому варианту методом пополнения. Поясним заполнение таблицы И,19. В строках 1 — 4, 7 — 10. 13 — 16, 19 — 22 последовательно записываются матрицы 5, 5,, 5 и 5>. Строки. совпадающие со строками единичной матрицы, целесообразно вписать в схему заранее. В строках б.
11, 17 и 23 записываются >(г-е строки матриц 5„,, в строках 6,12, 18 и 24 сов)а >) ответствующие множители ' „,, В тех >ке строках, слева от 1+ с~"„» ' схемы, записываются знаменатели !+сад . Наконец, в строках (в-1) 26 — 28 записывается матрица 5„=А '. Для контроля к каждой матрице 5» пристраивается столбец о„», составленный из строчных сумм. Суммируются также элементы (в) (в — » строк.
составленных из множителей — . Контрольные столбцы оа 1+с!,' ') (за исключением одного элемента, всегда равного единице) связаны соотношением ГЛАВА !Н ИТЕРАЦИОННЫЕ МЕТОДЫ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ УРАВНЕНИЙ Перейдем теперь к описанию итерационных методов решения систем линейных уравнений. Эти методы дают решение системы в виде предела последовательности некоторых векторов, построение которых осуществляется посредством единообразного процесса, называемого процессом итераций. В современной литературе описано большое количество итерзционных методов, основанных на различных принципах.
Как правило, вычислительные схемы этих методов просты и удобны при использовании вычислительной техники. Однако каждый итерационный процесс имеет свою ограниченную область применимости, так как, во-первых, процесс итераций может оказаться расходящимся для данной системы и, во-вторых, сходимость процесса может быть настолько медленной, что практически оказывается невозможным достигнуть удовлетворительной близости к решению. Отметим, что хотя задача обращения матрицы эквивалентна решению л частных систем с одной и той же матрицей, итерзционные методы редко употребляются для этой цели.
Настоящая глава посвящена описанию общих принципов построения итерационных процессов, детальному рассмотрению простейшего итерационного процесса — метода последовательных приближения в его различных модификациях и координатным релаксационным методам. й 29. Принципы построения итерационных процессов Основные итерационные процессы для решения линейных систем могут быть описзны посредством следующей общей схемы. Пусть дана система линейных уравнений АХ= Р (1) с неособенной матрицей А. Строится последовательность векторов Х~), ХП), ..., Х~").... по рекуррентным формулам Х(а) = Х(а-1)+ Н(й) <Р— АХ(в-1)) (2) $291 пеинципы постговния нтвгьцнонных пеоцвссов 205 где Н , Н , ... — некоторая последовательность матриц, Х (1) (о) (о) начальное приближение, вообще говоря, произвольное.
Различный выбор последовательности матриц Н("> приводит к различным итерационным процесса м . Итерационные процессы, протекающие по формуле (2), обладают тем свойством, что для каждого из них точное решение Л является неподвижной точкой. Это значит, что если за начальное приближение Х( > взято Х", то все последующие приближения будут также (о> равны Х". Ооратно, всякий итерационный процесс, для которого Х' является неподвижной точкой, протекающий по формулам Х(л> Сге)х(о-Н+ 7()'> 13) где С последовательность матриц, Л~ > последовательность векто(в) (а> ров, может быть представлен в виде (2). Действительно, для Х' имеем х'= с' )х*+л» ), откуда Х(о> = Х + Сйн (Х"-'> — Х') —.
Х'"-"+ (Сыо — Е) (Х"-'> — Х ) = = Х('-"+ (Е С(')) А-' А(Х* Х(а-')) = =Х( ")+Н( >(à — АХ( '>) при Н( )=(Š— С( )) А '. Нетрудно дать необходимые и достаточные условия для того, чтобы итерационный процесс (2) сходился к решению при любом нача.чьном векторе. Действительно, Х вЂ” Х( ) =- Х' — Х( ) — Нйо(АХ* — АХ(а" ц),— =(Š— Н( )А)(Л"' — Х ~ '>). Отсюда Л вЂ” Х =(Š— Н( >А)(Š— Н(ь ~)А) ... (Е Н(')А)(Л Х(о)) Для того. чтобы Л вЂ” Х -+0 при любом начальном векторе Л', (о) -ко) необходимо и достаточно (см. й 13, п. 1). чтобы матрица У(аб =(Š— Н( ~А)(Š— Н( >А) ... (Š— Н( )А) стремилась к нулю, для чего, в свою очередь, достаточно, чтобы любая норма матрицы г стремилась к нулю.
Конечно, выведенное условие лает лишь общую точку арения для построения условий сходимости конкретных итерационных процессов. 206 итввдционныз мвтоды ввшяния линвйных систвм (гл. ш Простейшими среди итерационных процессов являются с т а ц и о- (Ф) н а р н ы е итерационные процессы, в которых матрицы Н не зависят от номера шага л. В частности, при Н )= Е получается клас(а) си ческий процесс последовательных приближений. Любой стационарный процесс с Нф Е можно рассматривать как процесс последовательных приближений, примененный к равносильной системе НАХ= НР, так сказать „подготовленной" к применению метода последовательных приближений.
Конечно, осуществлять такую подготовку на самом деле обычно нет необходимости, и такого рода рассмотрение стационарных процессов лишь дает удобное средство для их теоретического исследования. Близкими к стационарным итерационным процессам являются ц и кл и ч е с к и е, в которых матрицы Н( ) периодически повторяются через (и) некоторое число р шагов. Ясно, что из каждого циклического процесса можно получить равносильный ему стационарный, принимая аа один шаг стационарного процесса результа~ применения полного цикла из р шагов исходного циклического процесса. Нестационарные итерационные процессы, в свою очередь, можно подразделить на два типа.
Это, во-первых, нестационарные итерационные процессы в буквальном смысле, когда изменение матрицы Н( ) (ю осушествляется на каждом шагу. Во-вторых, сюда можно включить стационарные процессы с ускорением сходимости посредством замены, время от времени, стационарной матрицы Н, определяющей процесс, на некоторые, специальным образом подобранные, матрицы Н( ).
Выбор матрицы Н для стационарного процесса и матриц гг ) для ° Я) нестационарного может осушествляться многими различными способами на основании различных принципов. Возможно построение матриц Н( ) так, чтобы итерзционный про(з) цесс сходился к решению для возможно более широкого класса систем уравнений. Возможнз противоположная точка зрения, в силу которой при построении матриц Н максимально используются част(й) ные особенности данной системы для получения итерзционного процесса, обладаюшего быстрейшей сходимостью. Естественно, что для применения итерационного процесса, построенного исходя из последнего принципа, нужно располагать возможно большей информацией о матрице коэффициентов системы, в частности о расположении ее собственных значений.
Важным принципом построения итерационных процессов является принцип релаксации. Под этим понимается принцип выбора мат' (а) риц Н( ) из некоторого заранее очерченного класса матриц так, чтобы метод последовательных пРиБлижений 207 % ЗО) на каждом шагу процесса уменьшалась какая-либо величина, характеризующая точность решения системы. Среди релаксационных методов наиболее разработаны к о о р д инатиые, в которых матрицы гФЮ подобраны так, что на каждом шагу меняются одна или несколько компонент последовательных приближений, и градиентные, в которых матрицы гг являются ,,кю скалярными.
О точности приближенного решения Х системы АХ= Р естественно судить по величине (в том или другом смысле) векторз ошибк и г'=Х* — Х. Однако вектор ошибки не может быть вычислен без знания точного решения системы и может лишь оцениваться. Вектором, характеризующим точность приближенного решения Х системы АХ=Р, может служить также вектор не вязки (невязка) г = — Р— АХ.
Ясно, что г = АУ, Таким образом, релаксация может быть построена на уменьшении любой нормы каждого из этих векторов. При положительно-определенных матрицах А удобной мерой точности является так называемая функция ошибки 7 (Х) = (АГ, 1') = (1', г) = (А г. г). В силу положительной определенности А всегда У'(Х) )~ О, причем 7"(Х) =О только прн Х=Л . Ясно, что 7" (Х) = (Х" — Х, Р— АХ) = (Л, Р) — (Х, Р) — (Л, АХ) + (Х, АХ) = =(АХ, Х) — 2(Х, Р)+(Х', Р). функция ошибки не может быть вычислена, если не известно точное решение. Однако ее значения лишь постоянным слагаемым отличаются от значений функционала )в(Х)=(АХ, Х) — 2(Х, Р), которые могут быть вычислены без знания Х'. Поэтому мы можем судить об убывании функции ошибки сравнивая соответствующие значения функционала ув(Х). Другим важным принципом построения итерзционных процессов является принцип последовательного „и о д а в л е и и я к о и п о н е н т" вектора ошибки в разложении его по собственным векторам матрицы коэффициентов системы.
Релаксационным градиентным методам будет посвящена глава ЧП. В главе 1Х будут рассмотрены методы, основанные на идее подавления компонент. и ЗО. Метод последовательных приближений. Наиболее простым итерационным процессом является процесс последовательных приближений. Под процессом последовательных приближений понимается следующий итерационный процесс, Система уравнений 208 итегоционныз мвтоды вешания линзйных аистам [гл.
ш АХ= Р записывается в виде Х=ВХ+О. гле В = Š— А, О = Р и последовательные приближения вычисляются по формуле х<") = вх<з "+ о, (2) начинзя с некоторого исходного приближения Х<), которое может <о) выбирзтьс я, вообще говоря, произвольно . Очевидно, что процесс послеловательных приближений является частным случаем общего итерационного процесса (2) 3 29; именно зто будет стационарный процесс, в котором Н = Е .
Действительно, Х' '=(Š— А)Х< ')+О=Х<". "+[Р— АХ' ')), а) Легко дать формулу для выражения Х непосредственно через начальное приближение Х'). Именно <о) Х"'= ВьХ'"'+ [В+В+ ... +В"-') а. (3) Действительно, при й = 1 зто верно, а при остальных й формула легко проверяется методом математической индукции. Отметим, что если процесс последовзтельных приближений сходится, то он сходится к решению системы. Действительно, если Х' -+Х*, <ь) то предельный переход в равенстве Х<ь) ВХ<ь-ц+ й дает Х*=ВХ*+О, т. е. Х* улозлетворяет двиной системе. Теорема а0.1. Для сходимости процесса последовательных приближений при любом начальном векторе Х необходимо и <о) достаточно, чтобы все собственные значения матрицы В были бы по модулю меньше единицы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
