Численные методы. Ионкин (2012) (неоффициальные) (косяки есть) (1160437), страница 3
Текст из файла (страница 3)
, ym );19Для того, чтобы нормировать это пространство, нужно ввести скалярное произведение и норму (пространство H может быть как вещественным, так и комплексным).Введем скалярное произведение векторов x и y:(x, y) =mXxi y ii=1Если допускаем и унитарное пространство, то(x, y) =mXxi y ii=1Тогда введем норму: (которая известна из курса линейной алгебры как евклидованорма):mX 121x2ikxk = (x, x) 2 =i=1Эту норму математики также часто называют среднеквадратичной нормой. Заметим,что это не сильная1 норма.Рассмотрим самосопряженный линейный оператор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;1Более сильную норму принято считать такую, в которой близость двух векторов будет болеежесткой.Например, норма в C будет более сильной, чем в L2 , так как в C близость векторов будетпокоординатная(поточечная).2Как у Маяковского «Партия и Ленин — близнецы-братья», так и у нас слова линейный оператори матрица отныне будут нести один и тот же смысл.203.
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 ∈ HC + C∗ C − C∗+. Тогда:Представим оператор C в виде суммы22(Cx, x) = (C + 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.21Тогда, воспользовавшись тем, что xn = V n + x, перепишем уравнение (2) черезвектор погрешностиV n+1 − V nB+ AV n = 0,(4)τгде 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 и изучает первая теорема, которую мы сейчас сформулируем.Теорема 1. Итерационный метод (2) решения задачи (1) сходится при любом начальном приближении тогда и только тогда, когда все собственные значения матрицы перехода S по модулю меньше единицы|λS | < 1,∀ x0Замечание. Теорема, конечно замечательная, и казалось бы, владея техникой нахождения собственных значений оператора, мы бы с легкостью все решали. Однакоалгебраические многочлены до четвертой степени математики решать умеют, авыше, как доказано Абелем и Галуа, вообще в радикалах не разрешимы. Поэтому,на самом деле, эта замечательная теорема для применения практически не годна - мы ей просто не сможем воспользоваться, кроме каких-нибудь простенькихслучаев.Рассмотрим теорему Самарского о достаточных условиях сходимости итерационного метода.
Понятно, что это не критерий, и, если эти условия не выполнены,то сходимость все-равно может иметь место. Зато условия, которые будут указаны,являются проверяемыми, и, применяя их к конкретной задаче, можно с уверенностьсказать, что метод сходится.22Теорема 2 (Самарского). Пусть H — вещественное пространство, A = A∗ > 0,где A — матрица системы (1), τ > 0 и выполнено матричное неравенство:B − 0.5 τ A > 0(6)Тогда итерационный метод (2) решения системы (1) сходится в среднеквадратичной норме при любом начальном приближенииkxn − xk =mX! 12(xnj − xj )2j=1−−−→ 0 ,n→∞∀x0Доказательство: Введем числовую последовательность yn = (AV n , V n ) > 0. Дляначала докажем, что она монотонная.
Для этого рассмотрим yn+1 :noyn+1 = (AV n+1 , V n+1 ) = V n+1 = SV n =no= (ASV n , SV n ) = S = (E −τ B −1A) == ( A(E − τ B −1A)V n , (E − τ B −1A)V n ) == (AV n , V n ) − τ (AV n , B −1 AV n ) + (AB −1 AV n , V n ) − τ (AB −1 AV n , B −1 AV n ) = ∗Итак, первое слагаемое по определению есть yn , рассмотрим вторую часть равенства.
Так как пространство H вещественное, то скалярное произведение коммутативно, поэтому(AB −1 AV n , V n ) = (B −1 AV n , A∗ V n ) = (B −1 AV n , AV n ) = (AV n , B −1 AV n )Тогда получим∗ = yn − τ 2(AV n , B −1 AV n ) − τ (AB −1 AV n , B −1 AV n ) =no= (a, b) − α(c, b) = (a − αc, b) = y n − 2τ (B − 0.5τ A)B −1 AV n , B −1 AV nТаким образом мы получили тождествоyn+1 − yn+ 2 (B − 0.5τ A)B −1 AV n , B −1 AV n = 0,τв котором оператор (B − 0.5τ A) положительный по условию, а следовательно и всескалярное произведение неотрицательно:(B − 0.5τ A)B −1 AV n , B −1 AV n > 0Отсюда следует, чтоyn+1 6 yn ,что и означает монотонность последовательности yn .А значит, согласно теореме Вейерштрасса, у последовательности существует предел y:∃ lim yn = yn→∞23Мы доказали, что введенная числовая последовательность yn является монотонной и ограниченной снизу, а значит, имеет предел.
Первая часть теоремы доказана.Чтобы приступить ко второй части доказательства, нам понадобится доказатьсвойство положительно определенного линейного оператора, которое сформулируемв виде задачи.Задача. Пусть H — вещественное пространство, C — положительный линейныйоператор. Доказать, что ∃ δ, такое что:(Cx, x) > δkxk2Итак, воспользовавшись данным свойством, можем сказать, что существует такая константа δ, что(B − 0.5τ A)B −1 AV n , B −1 AV n ) > δ kB −1 AV n k2Теперь, вспомнив ранее полученное тождество, можем записатьyn+1 − ynyn+1 − yn+ 2δ kB −1 AV n k2 6+ 2 (B − 0.5τ A)B −1 AV n , B −1 AV n = 0ττОбозначим для удобстваW n = B −1 AV n(7)Отсюда видно, что если устремить n к бесконечности, то норма вектора W nустремится к нулюlim kW n k = 0n→∞А теперь выразим погрешность через введенный нами вектор.
Для этого домножим равенство (7) слева сначала на B, затем на A−1V n = A−1 BW nТак как норма произведения операторов не превосходит произведения их норм,то, оценив погрешность, получим, что она стремится к нулю при n стремящемся кбесконечностиkV n k 6 kA−1 Bk·kW n k −−−→ 0n→∞Так как нигде в доказательстве на начальное приближение мы не опирались, тооно произвольное. СледовательноkV n k = kxn − xk =mXj=1! 21(xnj − xj )2−−−→ 0 ,n→∞∀x024Следствие 1.
Пусть A = A∗ > 0.Тогда метод Якоби сходится в среднеквадратичной норме при любом начальном приближении, если выполнено операторное неравенство2D > A,где A = R1 + D + R2 ,D = diag(a11 , a22 , . . . , ann ).Доказательство: Положим, B = D и τ = 1. Тогда перепишем уравнение (2) в видеD(xn+1 + xn ) + Axn = fПо теореме Самарского метод сходится, еслиB − 0.5τ A > 0или в нашем случаеD − 0.5A > 0,а это выполняется в силу условия. Следовательно, метод Якоби сходится.Следствие 2.
Пусть самосопряженная положительно определенная матрицаA = A∗ > 0 является матрицей со строгим диагональным преобладаниемaii >mX|aji |(8)j=1i6=jТогда метод Якоби сходится при любом начальном приближении в среднеквадратичной норме.Доказательство: Покажем, что если есть строгое диагональное преобладание, товерно матричное неравенство2D > A,которое доказывает сходимость метода (согласно следствию 1). Рассмотрим квадратичную форму (Ax, x):mm1X1X2|aij |·|xi | +|aij |·|xj |2 =(Ax, x) =aij xi xj 6|aij |·|xi |·|xj | 622i,j=1i,j=1i,j=1i,j=1mXmXmmnoX1X2= aij = aji = (|aij |·|xi | )·2 =|aij |·|xi |22 i,j=1i,j=1Выделим отдельно суммирование по индексу i:(Ax, x) 6mXi=1x2immmo XX nXaii +|aij | <|aij | < aii <2aii x2i = (2Dx, x).j=1i6=jj=1i6=ji=125Таким образом, мы получили, что(Ax, x) < (2Dx, x),откуда следует, что2D > AСледовательно выполняется условие следствия 1, и итерационный метод Якобисходится при любом начальном приближении.Задача.
Пусть A = A∗ > 0.Доказать, что aii > 0, i = 1, m.Следствие 3. Пусть A = A∗ > 0.Тогда метод Зейделя сходится в среднеквадратичной норме при любом начальном приближении.Доказательство: По определению метода Зейделя имеем:τ = 1,B = D + R1 .Исходя из условия теоремы Самарского, для того, чтобы сходился метод Зейделя, достаточно выполнения неравенстваB − 0.5τ A > 0.Докажем это.Распишем матрицы A и B:1D + R1 − (R1 + D + R2 ) > 02⇓D + R1 − R2 > 0⇓(D + R1 − R2 )x, x > 0⇓0 < (Dx, x) + (R1 x, x) − (R2 x, x) = (Dx, x) + (R1 x, x) − (R1∗ x, x) = (Dx, x)Откуда получаем, что(Dx, x) > 0Если матрица самосопряженная и положительно определенная, то все ее диагональные элементы больше нуля.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
