Бабенко - Основы численного анализа (947491), страница 102
Текст из файла (страница 102)
< г + Щ, 6 6) — ((Ь( ) где б = (1 + 6) е(пв + 8п)/2. Последнее неравенство есть следствие оче- видного неравенства и < ~4 +(1+8) -~~,( т2 — у') = ~4 +(1+ 6)е 1=1 Поскольку й — 1 (/А „+ 6) — (,'снос) = 6 ~~ ф/, + 6) (!А!, ), 1=О то при условии, что (и) Заметим, что последовательность матриц (1, 1) зависит от вектора т1 - хо. Таким образом, имеем точное равенство 496 Глава д. Творил игавраций и жегаодм решения нвкотпормх задач получим неравенство Л ... Л, ь 1, < 1, и, следовательно, последовательность, определяемая по формуле (9), стремится к нулю.
Чтобы это увидеть, достаточно, пользуясь ассоциативным законом для умножения матриц, сгруппировать сомножителн в произведении (9) следующим образом: хт о т — 1 = Лп — 1 ° Лгь-1(й~.ь ° ь0.— Овз-1) (1 ь ° Л1)(х3 хе) ° где г — -- ((т — 1)/дав. Выполнимость условия (10) зависит не только от спектра матрицы А, но и от ее структуры. Если ее собственные значения полупростые,. то такое значение показателя й может быть небольшим.
Но еыи матрица А есть жорданова клетка порядка и, то й =.. и, и, хотя условие (10) и выполнено, оно не обеспечивает практической сходимости последовательности (х — х„, В самом деле., рассмотрим в качестве примера матрицу А, с которой мы имели дело в п. 3 3 1. Взяв В = Е,', получим, что 1. = Š— А, и, таким образом, весь спектр матрицы Л сводится к единственной точке Л = О.
С точки зрения теоремы 1 это очен1 хороший случай. Однако в п. 3 з 1 было видно, что, ограничиваясь довольно скромными размерами матрицы и положив и = 20, а = 5, мы, решая систему, получали решение с огромными погрешностями. Что будет происходить, если для решения использовать метод простых итерацпйу Поскольку матрица Т, имеет вид то легко подсчитать, что Ь~ имеет элементы, отличные от нуля, лишь в позициях (1, й — 1), (2, й вь 2),...
и каждый из этих элементов равен ( — а)ь. С учетом округлений получим Л,...Л,=Та ЛХь и тогда, принимая во внимание вид матриц Лы даваемый формулой (8), будем иметь, при а > 0 ~Л1а', ( д ~~ (а ч- Л)ь '"дат, и, следователь~о.при й ~ (и — 1 хьч1 — хь ~, =! Ль... Л1(х1 — хо) ! = аь,'х1 — хо(„. Таким образом, если а > 1, по не настолько велико, чтобы наступило псреполяение,когда й = и, то сходимости итераций все равно не будет.
0 5. ХХтераииоиные методы ре1аения систем линейиыт уравнений 497 В самом деле, поскольку Е" = О, то т; 1 — яо = Е Е1(я1 — то) — 17 (тл — то) и М„(т1 — яв) не нуль. Поэтому для последующих и, итераций получится аналогичная каргина, которая, очевидно, повторится сколько угодно раз. Таким образом, мы имеем пример, когда условия теоремы выполнены., а итерации не сходятся. Если выполнено условие (10), то на основании неравенства (11) можно получить оценку погрешности с учетом погрешностей округления.
Однако она будет груба, и имеется более простой и элегантный способ определения погрешности. Прежде всего возникает вопрос: когда кончать итерационный процесс? Одно из возможных разумных условий состоит в том, что, задавшись константой во, итерации проводить до тех пор, пока не будет выполнено неравенство ~я — я 1~, < ео.
Вычислив затем х по формуле лт - (мт Ят-1) ~ (Ят-1 то "2) чз ° ° ! (г1 00) ейле, мы можем определить невязку (используя двойную точность) которая в данном случае дает правильное представление о погрешности, поскольку я -- б =- (Š—. 1) 11: следовательно, в тех случаях, когда норма (Е -- Е) невелика, мы получим достоверные данные о погрешности, используя неравенство Последним неравенством целесообразно пользоваться, если Д, < 1, и тогда '(Š—. Е) '~ < (1 — Е~ ) Иногда при решении систем линейных уравнений применяют итерационный процесс, называемый итерационным методом Зейделл.
Суть его состоит в следующем: механически разбиваем матрицу системы А на сумму матриц В=(ь, ),где!1,. =а, (1>у), 61 =0 (1<у) ис=(г, ), где сб = а, (1 < у), си — — 0 (1 > у). Ясно, что А = В+С, Затеи итерации выполняем по правилу Вт" 19Ст"=а., п=0,1.... вектор начальных данных ло определяем из дополнительных соображе- ний. 3 а д а ч а 1. Найдите необходимые и достаточные условия сходнмости метода Зейделя. 498 Глава д. Тео!тая итаерачий и лэетаоды решения некотаорвтх задач 3. Оптимальный итерационный процесс. Мы видим, что при организации итерационного процесса решения системы (1) существенное значение имеет местоположение спектра матрицы А и ее структура. Так, простота элементарных делителей матрицы А играет существенное значение в вопросах сходимости итерационных процессов. Поэтому лля частных классов матриц, таких, иапримор, как класс симметрических матриц, можно получить более тонкие результаты о сходимости итерационных процессов.
Допустим, что спектр матрицы А расположен на отрезке (т, ЛХ) веществеяной прямой, причем 0 < т < ЛХ! такого рода информацией мы располагаем, когда система линейных уравнений получена в результате дискретизации эллиптической задачи. Тогда можно построить итерационный процесс следующего вида: хо = х, т э- о(а — Ах, т), р = 1, 2,..., (12) где о некий параметр. Если Л собсгвенное значение матрицы А„то, согласно теореме 1т н нужно выбрать так, чтобы !1 — Лз тл' ,< 1, а поскольку это неравенство должно выполняться для любого собственного значения, то нужно, чтобы шах,1 — Ло( < 1. Отсюда следует, что о Е (О, 2ЛХ т).
ле,'от, те! Легко найти значение о, для которого этот максимум имеет наименьшее значение. Линейная функция '! — Ло достигает своего максимального по модулю значения на одном из концов отрезка уп, ЛХ). Если на концах этого отрезка при некотором о эта линейная функция принимает значения, равные по модулю и противоположные по знаку, го это и будет экстремальный случай. Поэтому о будем искать из уравнения 1 — от .=.
— (1— — нЛХ), откуда н .—.. 2(ЛХ р т) т, а ЛХ вЂ” ш шах ~! — оЛ = ли (, и! ' ЛХ + тп Дпя симметрической матрицы А из формулы х,— с — --(Х вЂ” пА) (х, т — ~)т где с -- решение системы (1), следует, что ~х — ф~в <',Х .. оА,з~х ...т - ~' — ~1 — оЛ ( ,'х где 1 — нЛ есть максимальное по модулю собсгвенное значение матри- цы Х вЂ” оА. Поэтому !хи 4/2 ~< !х~ — 1 ч з вт ( ) !хв ~!вт (13) и, следовательно, данный процесс простой итерации сходится. Однако, если ЛХ» т (а именно этот случай реализуется при решении краевых задач), сходимость будет очень медленной, н возникает настоятельная необходимость видоизменить процесс итераций так, чтобы он сходился максимально быстро.
з 5, Итерационные методое реиеспин систем, линейных уравнений 499 В практике вычислений играет роль и характер сходимостгь Желательно, чтобы процесс не только сходился, но чтобы сходимость имела монотонный характер, а не была колебательной. Желание иметь монотонный характер сходимости вызвало к жизни принципы релаксации. Основная идея их состоит в том, чтобы на каждом шаге итераций понижать значение соответствующей меры погрешности. Первое очевидное ссюбражопие состоит в гом, чтобы вместо формулы (12) использовать более общую формулу 114) хо '— ' хы- 1 — ' по .1го.-ы и = 1, 2,..., и распорядиться параметрами по, ..., о„1 так, чтобы величина хо — с,'я бьша минимальной; на1юмним, что в формуле (14) г, с зго невязка (и — 1)-го шага: го з = а — Ах, и Иная идея состоит в том, чтобы воспользоваться формулами более общего типа, скажем, е1 а'„, = С т ~ Росххо е, н = 1, 2,.
(15) где Ьхо —.. х 1 — т„„С„, Р„- некоторые матрицы. формула (15) определяет итерационный процесс второго порядка. Ясно,что можно ввести итерационные процессы более высоких порядков,и вполне понятно,как это делать. Мы будем рассматривать только процессы не выше второго порядка. Если Юо =- О, то формула (15) определяет процесс первого порядка, скалярный случай которого (матрицы Со скалярные) уже рассмотрен вылив. 3 ад а ч а 2.
Укажите вид матриц С„Р, при которых итерационный процесс второго порядка сводится к алгоритму исключения Гаусса. Рассмотрим случай скалярного итерационного процесса второго порядка, получающегося, если положить С, = с,7., Р, = Н„7 и тем самым е1хо =сот„+д Ьхо ы и=1, 2, (16) Если предположить, что до — -- О, то несложно убедиться, что х, — хо является линейной комбинацией векторов го, Аго, ..., .4о то, т.
е. х, = хо — Р— АА)го; (17) хоо1 = хо+ Ро — г(А)го+с [го — АР— 1(А)го] р 4о[Ро..1(А) — Ро — з(А)]го, т.е. х ге — "- хо — Р (А) го. Погрещность вектора хо определяется следую- щим образом: поскольку С .= 4 .-. Р„1(А)~а — Ас), то х, — ~ = [7 — Р, 1(А) (хо — ~), (18) где Р, 1 —. многочлен степени и — 1.
Это соотношение очевидным образом доказывается по индукции, поскольку из формулы (1о) непосредственно следует,что 500 Глава 3. Творил итаераций и леетоди решеиил иеяоторват задач и если одновременно с многочленами Ро з ввести многочлены погрешностей В (Л) = 1 — ЛР г(Л), то из форргулы (18) следует, что (19) Отметим, что многочлены погрешностей удовлетворяют соотношению В,(0) =- 1. (20) коз — К (Лз ) дз (21) и поэтому значения В,(Л ) многочлена погрешности указывают, насколько подавлена первоначальная погрешность после и-го итерационного шага.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
