Конспект лекций - 3ий поток, лектор - Ионкин (1113828), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

Перепишем равенство (2) следующим образом:i−1Xaij xj + aii xi +j=1mXaij xj = fi ,i = 1, m.j=i+1Тогда, отсюда можно выразить xi :fi −xi =i−1PmPaij xj −j=1aij xjj=i+1aii,c предположением, что aii 6= 0.Обозначим xni — n-я итерация i-й координаты.Чтобы организовать метод Якоби, слева «навешивают» итерацию n+1, а справасобирают все с n-ой итерацией.fi −xn+1=ii−1Paij xnj −j=1mPj=i+1aiiaij xnj,(3)где n = 0, 1, 2, .

. . , x0 — задано.В каждом конкретном итерационном методе выбор начального приближенияявляется самостоятельной задачей.Понятно, что никакой процесс не может продолжаться бесконечно долго, нужнобудет где-то оборвать это действие. Заканчиваем итерационный процесс тогда, когдадостигается оценка:kxn − xk < ε15Запишем метод Зейделя:fi −i−1Paij xn+1−jj=1xn+1=imPaij xnjj=i+1aii,(4)где n = 0, 1, 2, . . . , x0 - задано.Формулу (4) можно так же реализовать по явным методам.

Рассмотрим этотспособ.Положим i = 1. Найдем первую координату (n + 1)-ой итерации:f1 −mPa1j xnjj=2xn+1=1a11Найдем вторую координату:f2 − a21 xn+1−1mPa2j xnjj=3xn+1=2a22И так далее. То есть, организуя вычислительный процесс с первой координаты,можно найти все значения вектора x по явным формулам для (n + 1)-й итерации.Таким образом, метод Зеделя реализуется по явным формулам. При изученииитерационных методов важно не упускать из виду два вопроса: первый - сходимостьметода и условия этой сходимости, второй - получение оценки скорости сходимостиметода.Для исследования этих вопросов удобно рассматривать системы в матричномвиде.

Любую матрицу мы можем представить в виде суммы трех матриц R1 +D+R2 ,где00..R1 = .  — нижнетреугольная матрица c нулевой диагональю,aij0a110...D= — диагональная матрица,0amm0aijR2 =  . . . — верхнетреугольная матрица с нулевой диагональю.00Тогда перепишем уравнение (1):R1 x + Dx + R2 x = f⇓16Dx = f − R1 x − R2 xЕсли предположить, что матрица D имеет обратную, а это как раз и требуетвыполнения условия aii 6= 0, то тогда, домножив слева на матрицу D−1 , получаемx = D−1 f − D−1 R1 x − D−1 R2 x.Итак, организуем итерационный процесс для метода Якоби и Зейделя.МЯ:xn+1 = D−1 f − D−1 R1 xn − D−1 R2 xn(5)МЗ:xn+1 = D−1 f − D−1 R1 xn+1 − D−1 R2 xn(6)Dxn+1 = f − R1 xn − R2 xn(7)(D + R1 )xn+1 = f − R2 xn(8)D(xn+1 − xn ) + Axn = f(9)(D + R1 )(xn+1 − xn ) + Axn = f(10)МЯ:МЗ:МЯ:МЗ:0где n = 0, 1, 2, . .

. , x — задано.Видно, что если есть сходимость, то сходится к решению нашей системы. Такматематики и пришли к каноническому виду двухслойного итерационного процесса.Определение. Канонической формой записи двухслойного итерационного методарешения системы (1) называется запись видаBn+1xn+1 − xn+ Axn = f,τn+1(11)−1где n = 0, 1, 2, . .

. , x0 — задано, τn+1 > 0 (итерационный параметр) и ∃Bn+1. ЕслиBn+1 = E, то метод (11) называется явным, в противном случае – неявным.Замечание. Если параметр τ и матрица B зависят от итерации, то метод называется нестационарным, иначе стационарным. Далее мы будем рассматриватьтолько стационарные методы.Отметим, что если Bn+1 – диагональная матрица, то метод реализуется по явнымформулам, хотя формально метод неявный.Рассмотрим еще один метод — метод простой итерации (метод релаксации).xn+1 − xn+ Axn = f,ττ >0n = 0, 1, 2, .

. . , x0 – задано.Если τ зависит от n, то получающийся методxn+1 − xn+ Axn = f,τn+1называется методом Ричардсона.17Попеременно треугольный итерационный метод (метод Самарского)Представим матрицу A в виде A = R1 + R2 , где0.5a110..R1 =  — нижнетреугольная матрица,.aij0.5amm0.5a11aij...R2 =  — верхнетреугольная матрица.00.5ammТогда попеременно треугольный итерационный метод имеет следующий вид:(E + wR1 )(E + wR2 )xn+1 − xn+ Axn = f,τ(12)где n = 0, 1, . .

. , x0 — задано, τ > 0, w > 0 – итерационные переметры.В данном методе имеется два итерационных параметра. С точки зрения алгоритма реализации, этот метод не сложнее, чем предыдущие, а по сходимости - напорядок лучше.Введем векторxn+1 − xn(E + wR2 )= W n+1τОпределение. Разность между правой и левой частями решаемой системы называется невязкой.В нашем случае невязка имеет видf − Axn = rnТогда видно, что на первом этапе можем решать уравнение(E + wR1 )W n+1 = rnПравая часть известна, а (E + wR1 ) — нижнетреугольная матрица. Нахождение вектора системы с нижнетреугольной матрицей осуществляется по явным формулам,начиная с первой компоненты вектора W .Теперь, на втором этапе решаем уравнение(E + wR2 )V n+1 = W n+1 ,гдеxn+1 − xn.τНа третьем этапе (n + 1)-ю итерацию находим по формуле:V n+1 =xn + τ V n+1 = xn+1 .Таким образом, несмотря на то, что метод Самарского неявный с двумя итерационными параметрами, его реализация не представляет никакой трудности.18§6 Теоремы о сходимости итерационных методовРассмотрим матричное уравнение видаAx = f,(1)где A — матрица размера (m × m), |A| =6 0.Рассмотрим также двухслойный стационарный метод решения уравнения (1):Bxn+1 − xn+ Axn = f,τ(2)где τ > 0, существует обратная матрица B −1 , n = 0, 1, 2, .

. . , и задано начальноеусловие x0 .Когда мы говорим, что начальное условие задано, то это значит, что либо егонадо выбирать исходя из каких-то жестких условий, либо есть свобода выбора.Говоря о сходимости нужно четко понимать, по какой норме эта сходимостьполучается, поэтому нам необходимо ввести линейное нормированное пространство.Пуcть H - линейное пространство размерности m:dim H = mВозьмем два произвольных вектора x и y из этого пространства:x ∈ H,x = (x1 , x2 , .

. . , xm );y ∈ H,y = (y1 , y2 , . . . , ym );Для того, чтобы нормировать это пространство, нужно ввести скалярное произведение и норму (пространство H может быть как вещественным, так и комплексным).Введем скалярное произведение векторов x и y:(x, y) =mXxi y ii=1Если допускаем и унитарное пространство, то(x, y) =mXxi y ii=1Тогда введем норму: (которая известна из курса линейной алгебры как евклидованорма):m 12X1kxk = (x, x) 2 =x2ii=1Эту норму математики также часто называют среднеквадратичной нормой. Заметим,что это не сильная1 норма.1Более сильную норму принято считать такую, в которой близость двух векторов будет болеежесткой.Например, норма в C будет более сильной, чем в L2 , так как в C близость векторов будетпокоординатная(поточечная).19Рассмотрим самосопряженный линейный оператор2 D = D∗ > 0.

Введем новуюнорму в вещественном пространстве.Определение. Энергетическая норма - это норма, задаваемая соотношением1kxkD = (Dx, x) 2Замечание. Заметим, что требование самосопряженности здесь очень важно.Если бы матрица D не была самосопряженной, то скалярное произведение (Dx, x)было бы комплексным числом, а значит и связывать с нормой это произведениемы бы не имели права.Вспомним несколько принципиально важных понятий, с которыми связаныочень непростые переходы, которые будут использоваться в доказательствах последующих теорем:1.

D > 0 ⇐⇒ (Dx, x) > 0,∀x 6= 0;2. D > 0 ⇐⇒ (Dx, x) > 0,∀x ∈ H;3. D = D∗ > 0 =⇒ ∃ δ > 0 :(Dx, x) > δkxk2 ;Здесь легко понять, что δ будет связана с минимальным собственным значением, так как, если у нас самосопряженный и положительно определенныйоператор, то у него все собственные значения положительны и есть базис изсобственных векторов. Если разложить вектор x по базису из собственных векторов и заменить собственное значение на минимальное, то δ как раз им ибудет.4. Если D = D∗ > 0, то• ∃D−1 = (D−1 )∗ > 0;11• ∃D 2 = (D 2 )∗ > 0;11• ∃D− 2 = (D− 2 )∗ > 0.Задача. Пусть H — вещественное пространство, C — положительно определенный линейный оператор. Доказать, что(Cx, x) = (C + C∗x, x)2Решение: Для решения данной задачи воспользуемся следующими равенствами,верными для вещественного пространства H:(C ∗ x, x) = (x, Cx) = (Cx, x), x ∈ H2Как у Маяковского «Партия и Ленин — близнецы-братья», так и у нас слова линейный оператори матрица отныне будут нести один и тот же смысл.20Представим оператор C в виде суммы(Cx, x) = (C + C∗ C − C∗+.

Тогда:22C + C∗C − C∗C + C∗1C + C∗x, x)+(x, x) = (x, x)+ ((C ∗ x, x)−(Cx, x)) = (x, x), ∀x ∈ H22222Для того, чтобы мы могли говорить о сходимости, введем понятие погрешности.Определение. Вектор, видаV n = xn − xназывается погрешностью на n-ой итерацииТаким образом, для того, чтобы доказать, что итерационный метод сходится,нам необходимо показать, что в соответствующей норме погрешность на n-ой итерации будет стремиться к нулю при n стремящемся к бесконечностиlim kV n k = 0,n→∞(3)что и будет означать, что наше приближение xn будет стремиться к точному решениюx.Тогда, воспользовавшись тем, что xn = V n + x, перепишем уравнение (2) черезвектор погрешностиV n+1 − V n+ AV n = 0,(4)Bτгде n = 0, 1, .

. . , V 0 = x0 − x.Таким образом, приступим к изучению уравнения (4). Для этого обычно выражают n+1 итерацию через n, с условием того, что существует обратная к B матрица.Домножим слева уравнение (4) на B −1 :V n+1 − V n+ B −1 AV n = 0τВыразим отсюда погрешность на n + 1 итерацииV n+1 = V n − τ B −1 AV n = (E − τ B −1 A)V n = SV nТаким образом, мы получили матрицу S, которая связывает предыдущую итерациюс последующейS = E − τ B −1 A(5)Определение.

Матица S называется матрицей перехода от n-й итерации к(n + 1)-й.Нетрудно заметить, что сходимость и скорость сходимости вектора V n всецелозависит от свойств матрицы S, а именно от ее спектра. Именно эти свойства спектраматрицы S и изучает первая теорема, которую мы сейчас сформулируем.21Теорема 1. Итерационный метод (2) решения задачи (1) сходится при любом начальном приближении тогда и только тогда, когда все собственные значения матрицы перехода S по модулю меньше единицы|λS | < 1,∀ x0Замечание. Теорема, конечно замечательная, и казалось бы, владея техникой нахождения собственных значений оператора, мы бы с легкостью все решали. Однакоалгебраические многочлены до четвертой степени математики решать умеют, авыше, как доказано Абелем и Галуа, вообще в радикалах не разрешимы.

Поэтому,на самом деле, эта замечательная теорема для применения практически не годна - мы ей просто не сможем воспользоваться, кроме каких-нибудь простенькихслучаев.Рассмотрим теорему Самарского о достаточных условиях сходимости итерационного метода. Понятно, что это не критерий, и, если эти условия не выполнены,то сходимость все-равно может иметь место. Зато условия, которые будут указаны,являются проверяемыми, и, применяя их к конкретной задаче, можно с уверенностьсказать, что метод сходится.Теорема 2 (Самарского).

Характеристики

Список файлов лекций