1611688847-5b7354cc83380cb6c671f7c9dd5f83f8 (826648), страница 26

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

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

е. что направление спуска на «нулевомшаге» — это нулевой вектор.Доказательство проводится индукциейпо размерности пространства.Доказательство проводится индукциейпо размерности пространства.Прежде всего, построим базу индукции.Отметим, что для k = 1 невязки r (0) и r (1) ортогональны в силудоказанного Предложения. Также ортогональны s(0) и s(1) .Доказательство проводится индукциейпо размерности пространства.Прежде всего, построим базу индукции.Отметим, что для k = 1 невязки r (0) и r (1) ортогональны в силудоказанного Предложения. Также ортогональны s(0) и s(1) .Предположим теперь, что утверждение Теоремы справедливо длянекоторого k. Покажем, что оно верно также для k + 1.Доказательство проводится индукциейпо размерности пространства.Прежде всего, построим базу индукции.Отметим, что для k = 1 невязки r (0) и r (1) ортогональны в силудоказанного Предложения.

Также ортогональны s(0) и s(1) .Предположим теперь, что утверждение Теоремы справедливо длянекоторого k. Покажем, что оно верно также для k + 1.Нам необходимо доказатьhs(k+1) , s(j) iA = 0 для j = 1, 2, . . . , k,hr (k+1) , r (j) i = 0 для j = 0, 1, 2, . . . , k.Заметим, чтоhs(k+1) , s(k) iA = hs(k+1) , As(k) i = 0по построению метода сопряжённых градиентовЗаметим, чтоhs(k+1) , s(k) iA = hs(k+1) , As(k) i = 0по построению метода сопряжённых градиентовДалее, так как согласно (3)s(k+1) = −r (k) + υk+1 s(k) ,тоhs(k+1) , s(j) iA = hs(k+1) , As(j) i = −hr (k) , As(j) i + υk+1 hs(k) , As(j) i,где последнее слагаемое зануляется при j < kв силу индукционного предположения.Итак,hs(k+1) , s(j) iA = −hr (k) , As(j) i.С другой стороны, в методе сопряжённых градиентов, согласно (5),невязка изменяется какr (j) = r (j−1) − τj As(j) ,откудаAs(j) =1 (j−1)r− r (j) .τjС другой стороны, в методе сопряжённых градиентов, согласно (5),невязка изменяется какr (j) = r (j−1) − τj As(j) ,откудаAs(j) =1 (j−1)r− r (j) .τjПодставив в полученные ранее формулы, будем иметьhs(k+1) , As(j) i = −hr (k) , As(j) i1 (k) (j−1)=−hr , ri − hr (k) , r (j) i = 0,τjгде оба слагаемых в больших скобках раны нулюв силу индукционного предположения.Это доказывает A-ортогональность направлений спуска.Покажем теперь ортогональность невязок r (k) , k = 0, 1, 2, .

. . ,т. е. чтоhr (k+1) , r (j) i = 0 для j = 0, 1, 2, . . . , k.Покажем теперь ортогональность невязок r (k) , k = 0, 1, 2, . . . ,т. е. чтоhr (k+1) , r (j) i = 0 для j = 0, 1, 2, . . . , k.Прежде всего, отметим, чтоhr (k+1) , r (k) i = 0в силу доказанного ранее Предложения. Остаётся доказать,что для 0 ≤ j < k также имеем hr (k+1) , r (j) i = 0.Покажем теперь ортогональность невязок r (k) , k = 0, 1, 2, .

. . ,т. е. чтоhr (k+1) , r (j) i = 0 для j = 0, 1, 2, . . . , k.Прежде всего, отметим, чтоhr (k+1) , r (k) i = 0в силу доказанного ранее Предложения. Остаётся доказать,что для 0 ≤ j < k также имеем hr (k+1) , r (j) i = 0.По построению метода сопряжённых градиентовr (k+1) = r (k) − τk+1 As(k+1) ,и потому в силу индукционного предположенияhr (k+1) , r (j) i = hr (k) , r (j) i − τk+1 hAs(k+1) , r (j) i= −τk+1 hAs(k+1) , r (j) i.С другой стороны, так как в методе сопряжённых градиентовнаправления спуска на j-ом и (j + 1)-ом шагах связаны формулойs(j+1) = −r (j) + υj+1 s(j) ,можно выразить невязку r (j) через эти направления:r (j) = −s(j+1) + υj+1 s(j) .С другой стороны, так как в методе сопряжённых градиентовнаправления спуска на j-ом и (j + 1)-ом шагах связаны формулойs(j+1) = −r (j) + υj+1 s(j) ,можно выразить невязку r (j) через эти направления:r (j) = −s(j+1) + υj+1 s(j) .Подставляя результат в полученное ранее выражение дляhr (k+1) , r (j) i, получимhr (k+1) , r (j) i = −τk+1 hAs(k+1) , r (j) i= −τk+1 −hAs(k+1) , s(j+1) i + υj+1 hAs(k+1) , s(j) i .Но мы уже доказали, что направления спуска A-ортогональныдруг другу.

Следовательно, для j < khAs(k+1) , s(j+1) i = 0иhAs(k+1) , s(j) i = 0.В целом имеем,hr (k+1) , r (j) i = 0,как и требовалось.Но мы уже доказали, что направления спуска A-ортогональныдруг другу. Следовательно, для j < khAs(k+1) , s(j+1) i = 0иhAs(k+1) , s(j) i = 0.В целом имеем,hr (k+1) , r (j) i = 0,как и требовалось.Наконец, для j = 0 имеемr (0) = −s(1) ,так что в самом делеhr (k+1) , r (0) i = −τk+1 hAs(k+1) , r (0) i = τk+1 hAs(k+1) , s(1) i = 0.Это завершает доказательство Теоремы.СледствиеМетод сопряжённых градиентов для решения n × n-системылинейных уравнений с симметричной положительно-определённойматрицей находит точное решение не более чем за n шагов.СледствиеМетод сопряжённых градиентов для решения n × n-системылинейных уравнений с симметричной положительно-определённойматрицей находит точное решение не более чем за n шагов.Доказательство следует из следующих фактов:Размерность пространства Rn равна n.Невязки r (k) = Ax(k) − b, k = 0, 1, 2, .

. ., — ортогональныеи потому линейно независимы.Потому ненулевых таких невязок может быть не более n штук.Но на практике из-за неизбежных погрешностей вычисленийметод сопряжённых градиентов может не прийти к точномурешению системы за n шагов.Но на практике из-за неизбежных погрешностей вычисленийметод сопряжённых градиентов может не прийти к точномурешению системы за n шагов.Тогда целесообразно повторить цикл уточнения, превративалгоритм при необходимости в итерационный.

При этомXx = x(0) +ci s(i) ,iгдеx(0) — начальное приближение,s(i) , i = 1, 2, . . . , n, — векторы разложения решения,ci — коэффициенты разложения решения по ним.Верхний предел суммы может значительно превосходить n.Но на практике из-за неизбежных погрешностей вычисленийметод сопряжённых градиентов может не прийти к точномурешению системы за n шагов.Тогда целесообразно повторить цикл уточнения, превративалгоритм при необходимости в итерационный.

При этомXx = x(0) +ci s(i) ,iгдеx(0) — начальное приближение,s(i) , i = 1, 2, . . . , n, — векторы разложения решения,ci — коэффициенты разложения решения по ним.Верхний предел суммы может значительно превосходить n.Оптимизированный псевдокод метода сопряжённых градиентов,в котором количество векторно-матричных операций сведенок минимуму, приведён на следующем слайде.выбираем начальное приближение x(0) ;k ← 0;r(0) ← b − Ax(0) ;s(0) ← r(0) ;DO WHILE ( метод не сошёлся )g ← As(k) ;τk ←h r(k) , r(k) i;hs(k) , gix(k+1) ← x(k) + τk s(k) ;r(k+1) ← r(k) − τk g ;υk+1 ←h r(k+1) , r(k+1) i;h r(k) , r(k) is(k+1) ← r(k+1) + υk+1 s(k) ;k ← k + 1;END DOТеоремаЕсли A — симметричная положительно определённая матрица, топоследовательность {x(k) }, порождаемая методом сопряжённыхградиентов, сходится к решению x⋆ системы уравнений Ax = b излюбого начального приближения x(0) .Быстрота этой сходимости оценивается неравенствомk x(k) − x⋆ kA ≤ 2√√ !kµ√k x(0) − x⋆ kA ,√M+ µM−k = 0, 1, 2, .

. . , где µ, M — нижняя и верхняя границы спектраматрицы A.ТеоремаЕсли A — симметричная положительно определённая матрица, топоследовательность {x(k) }, порождаемая методом сопряжённыхградиентов, сходится к решению x⋆ системы уравнений Ax = b излюбого начального приближения x(0) .Быстрота этой сходимости оценивается неравенствомk x(k) − x⋆ kA ≤ 2√√ !kµ√k x(0) − x⋆ kA ,√M+ µM−k = 0, 1, 2, . . .

, где µ, M — нижняя и верхняя границы спектраматрицы A.Доказательство опускается.Его можно найтив продвинутых книгах по вычислительной линейной алгебре.Другая форма оценки сходимости —kx(k)⋆− x kA ≤ 2ppcond2 (A) − 1cond2 (A) + 1!kk x(0) − x⋆ kA ,k = 0, 1, 2, . . . , где cond2 (A) — спектральное число обусловленностиматрицы A.Другая форма оценки сходимости —kx(k)⋆− x kA ≤ 2ppcond2 (A) − 1cond2 (A) + 1!kk x(0) − x⋆ kA ,k = 0, 1, 2, . . . , где cond2 (A) — спектральное число обусловленностиматрицы A.Выписанные оценки не отражает все существенные особенностисходимости метода сопряжённых градиентов.Большое значение имеет конкретное расположение собственныхчисел матрицы системы, а не только наименьшее и наибольшееиз них.Оценка погрешности приближённого решенияРассмотрим вопрос об оценке погрешности приближённого решениясистем линейных алгебраических уравнений.Он практически важен сам по себе,а также в связи с условиями остановки итерационных методов.Оценка погрешности приближённого решенияРассмотрим вопрос об оценке погрешности приближённого решениясистем линейных алгебраических уравнений.Он практически важен сам по себе,а также в связи с условиями остановки итерационных методов.Мы предложим два простых способа оценки погрешностей,хотя в действительности их существует гораздо больше.Первый способ носит общий характер и может применятьсяв любых ситуациях, в частности, не обязательно в связис какими-то конкретными численными методами.Пусть x̃ — приближённое решение системы уравнений Ax = b,x∗ — её точное решение.Поскольку I = A−1 A и Ax∗ = b, то имеемkx̃ − x∗ k = A−1Ax̃ − A−1Ax∗ = A−1 (Ax̃ − Ax∗ )≤ A−1 Ax̃ − b,где матричная и векторная нормы согласованы друг с другом.Пусть x̃ — приближённое решение системы уравнений Ax = b,x∗ — её точное решение.Поскольку I = A−1 A и Ax∗ = b, то имеемkx̃ − x∗ k = A−1Ax̃ − A−1Ax∗ = A−1 (Ax̃ − Ax∗ )≤ A−1 Ax̃ − b,где матричная и векторная нормы согласованы друг с другом.Величина (Ax̃ − b) — это невязка приближённого решения x̃,которую мы можем вычислять непосредственно по x̃.Пусть x̃ — приближённое решение системы уравнений Ax = b,x∗ — её точное решение.Поскольку I = A−1 A и Ax∗ = b, то имеемkx̃ − x∗ k = A−1Ax̃ − A−1Ax∗ = A−1 (Ax̃ − Ax∗ )≤ A−1 Ax̃ − b,где матричная и векторная нормы согласованы друг с другом.Величина (Ax̃ − b) — это невязка приближённого решения x̃,которую мы можем вычислять непосредственно по x̃.Как следствие, погрешность решения можно узнать,найдя каким-либо образом или оценив сверхунорму обратной матрицы kA−1 k.Нередко какую-то информацию о значении kA−1 kможно получить из практики или из самой задачи.Нередко какую-то информацию о значении kA−1 kможно получить из практики или из самой задачи.Пример.Пусть A — симметричная положительно определённая матрица.Предположим, что известна нижняя граница её спектра,λ(A) ≥ µ > 0.Напомним, что аналогичную информацию о спектре матрицысистемы линейных уравнений мы использовали при оптимизациискалярного предобуславливателя в методе Ричардсона.ПредложениеЕсли λ — собственное число квадратной неособенной матрицы, тоλ−1 — это собственное число обратной матрицы, отвечающее томуже собственному вектору.ПредложениеЕсли λ — собственное число квадратной неособенной матрицы, тоλ−1 — это собственное число обратной матрицы, отвечающее томуже собственному вектору.Доказательство.

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

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