Д.П. Костомаров, А.П. Фаворский - Вводные лекции по численным методам (pdf) (1113729), страница 4
Текст из файла (страница 4)
Чтобы убедиться в- 13 этом, подсчитаем число обусловленности матрицы A , напишем с его помощьютеоретическую оценку (54) и сравним ее с фактическим результатом (58).Выпишем линейное преобразование y = Ax отвечающее матрице системыy1 = x1y2 = x1 + 0.01x2 ,при этомAx = x12 + ( x1 + 0.01x2 ) .2Наложим ограничениеx12 + x22 = 1 ,тогда в силу (43)Ax = max 2 x12 + 0.0001x22 + 0.02 x1 x2 , x12 + x22 = 1 .Если положить x1 = cosϕ , x2 = sin ϕ , то задача сведется к отысканию максимумавыраженияg (ϕ ) = 2 cos2 ϕ + 0.02sin ϕ cos ϕ + 0.0001sin 2 ϕ ,зависящего только от одной переменной ϕ , 0 ≤ ϕ ≤ 2π .Переходя к тригонометрическим функциям двойного угла2 cos 2 ϕ = 1 + cos 2ϕ , 2 sin 2 ϕ = 1 − cos 2ϕ , 2 sin ϕ cosϕ = sin 2ϕ ,сведем подрадикальное выражение к виду:1.00005 + 0.01sin 2ϕ + 0.99995 cos 2ϕДля комбинацииB1 cos 2ϕ + B2 sin 2ϕ = B12 + B2 2 cos(2ϕ − ϕ 0 ) , 0 ≤ ϕ ≤ 2π ,гдеϕ 0 = arctg ⎛⎜ B1 B ⎞⎟ , B1 = 0.99995 , B2 = 0.01,⎝2⎠максимальное значение равноB12 + B2 2 = 0.999952 + 0.012 .СледовательноA = 1.00005 + 0.999952 + 0.012 .С приемлемой точностью это число равно 2 : A ≈ 2 .Аналогичным образом находится норма обратной матрицы0 ⎤⎡ 1A −1 = ⎢, A −1 ≈ 100 2 .⎥⎣− 100 100⎦Таким образом, в данном примереM A = A ⋅ A−1 ≈ 200 .В результате теоретическая оценка (54) принимает вид:δxδf≤ 200xf(59)- 14 Она согласуется с результатом (58), который мы получили, непосредственно решаясистемы (56) и (57).В процессе решения задачи мы убедились в том, что подсчет числаобусловленности является сложной задачей, особенно с учетом того, что нужновычислять норму не только прямой, но и обратной матрицы.
Поэтому желательнополучить какие-нибудь конструктивные оценки этой важнейшей характеристикисистемы.2.4. Оценка числа обусловленности.Для числа обусловленности матрицы A справедливо неравенствоM A ≥ λmax / λmin ,(60)где λmin и λmax соответственно минимальное и максимальное по модулю значенияхарактеристических чисел матрицы A . Соотношение (60) корректно, поскольку в силуневырожденности матрицы λmin ≠ 0 .В самом деле пусть y - собственный вектор линейного преобразования,связанного с матрицей A , отвечающий λmax :Ay = λmax y ,тогдаλmax y = Ay ≤ A ⋅ y ,и, следовательно, поскольку y ≠ 0λmax ≤ A .Аналогичным образом для собственного вектора z , связанного с λmin , имеемAz = λmin zили1A−1z =z.λminОтсюда следует оценка1λmin≤ A−1 .Перемножая два последних неравенства, придем к утверждению (60).Если матрица симметричная A = A* , то все её характеристические значениявещественны, причем1A = λmax и A−1 =,λminпоэтому для таких матрицMA =λmax.λminИз полученной оценки для M A следуют два важных вывода:1) M A ≥ 1 ;(61)- 15 2) Число обусловленности тем больше, чем больше разброс характеристическихчисел матрицы.
Поэтому с увеличением размера матрицы, вообще говоря, еёобусловленность имеет тенденцию к ухудшению.Возвращаясь к рассмотренной выше задаче, без труда находим: λmin = 0.01 ,λmax = 1 и, следовательно, справедлива оценка снизуM A ≥ λmax / λmin = 100 ,причем точность этой оценки невысока, но порядок она передает правильно.В заключение данного параграфа еще раз отметим, что для систем уравнений сбольшой размерностью "хорошая" обусловленность ( M A 1) является скорееисключением, чем правилом и обычно приходится иметь дело с плохообусловленными матрицами ( M A 1 ), причем получение оценки числаобусловленности вызывает большие трудности.§3. Итерационные методы.3.1. Построение итерационных последовательностей.Мы видели, что процедура решения СЛАУAx = f(62)с плохо обусловленной матрицей A может приводить к существенным отклонениямполучаемого ответа от точного решения при незначительных возмущениях правойчасти. Однако появление таких возмущений неизбежно, например, припреобразовании вектора правых частей в методе Гаусса из-за ошибок округления привыполнении арифметических операций.
Чем выше порядок матрицы, тем большеможет оказаться результирующая погрешность.Этого недостатка лишены итерационные методы решения СЛАУ. При ихприменении ответ получается в процессе построения последовательных приближений(итераций) x k = {x1k , x2k ,K xnk } , сходящихся к решению системы (62) в пространстве Enс евклидовой нормой xlim x k = x(63)k →∞Здесь при записи вектора x k через его компоненты xik нижний индекс i означаетномер компоненты (1 ≤ i ≤ n ), верхний индекс k - номер итерации. Сходимостьпоследовательности x k к решению системы x означает, чтоlim x k − x = limk →∞k →∞(xk1− x1 ) + ( x2k − x2 ) + L + ( xnk − xn ) = 0 .222(64)Необходимым и достаточным условием предельного равенства (64) в конечномерномевклидовом пространстве En является покомпонентная сходимость:lim xik = xi , 1 ≤ i ≤ n .k →∞Сходимость обеспечивает принципиальную возможность получить в процессеитераций ответ с любой наперед заданной степенью точности.С итерационными последовательностями вы встречались.
Каждый следующийчлен такой последовательности выражается через предыдущие, уже известные. Если,например, формула для вычисления очередного члена последовательности имеет вид:- 16 -x k +1 = F ( x k , x k −1 ,K, x k −m+1 ) ,то говорят о m -шаговом итерационном алгоритме. В частности, в простейшем случаеочередной член последовательности x k +1 может выражается только через предыдущийxk :x k +1 = F ( x k ) .Такие итерационные алгоритмы называют одношаговыми.При обсуждении итерационных методов решения СЛАУ мы ограничимсялинейными одношаговыми алгоритмами, которые обычно записывают в стандартнойканонической форме:x − xkBk +1 k +1+ Ax k = f , det Bk +1 ≠ 0 , τ k +1 > 0 .(65)τ k +1В такой записи процесс характеризуется последовательностью матриц Bk +1 ичисловых параметров τ k +1 , которые называют итерационными параметрами.
Еслиматрицы Bk +1 и параметры τ k +1 не меняются в процессе итераций, т. е. не зависят отиндекса k , то итерационный процесс называется стационарным.Перепишем формулу (65) в виде(66)Bk +1x k +1 = Fk +1 ,гдеFk +1 = ( Bk +1 − τ k +1 Ak +1 ) x k + τ k +1f .(67)Мы видим, что построение очередной итерации сводится к решению системыуравнений (66) с правой частью (67), зависящей от предыдущей итерации x k .
Такуюзадачу приходится решать многократно, поэтому матрицы Bk +1 следует выбиратьдостаточно простыми. Если построение отдельных итераций будет соизмеримым посложности с решением исходной задачи, то метод окажется лишенным практическогосмысла.Наиболее прост в реализации итерационный процесс с единичной матрицей:Bk +1 = E . В этом случае формулы (66), (67) дают явное выражение очередной итерациичерез предыдущую:x k +1 = ( E − τ k +1 A ) x k + τ k +1f .(68)Из неявных итерационных методов выделим сравнительно легко реализуемыеметоды с диагональными матрицами: Bk +1 = Dk +1 и верхними или нижнимитреугольными матрицами: Bk +1 = Tk +1 .3.2. Проблема сходимости итерационного процесса.Итерационный процесс может быть использован для решения СЛАУ только приусловии сходимости. Для исследования его сходимости введем две характеристики.Первая из них – погрешность решения:z k = xk − x .(69)Смысл этого вектора ясен.
Сходимость итерационного процесса согласно (63) и (64)означает, что- 17 lim z k = 0 , lim zik = 0 , 1 ≤ i ≤ n .k →∞k →∞(70)Вторая характеристика – невязка:ψ k = Ax k − f .(71)Она показывает, насколько хорошо или, наоборот, плохо член итерационнойпоследовательности x k удовлетворяет исходной системе.Установим связь между z k и ψ k :ψ k = Ax k − f = A ( z k + x ) − f = Az k .(72)Можно также написать обратное соотношение:z k = A−1ψ k .(73)Из формул (72) и (73) вытекают оценки:ψ k ≤ A ⋅ z k , z k ≤ A−1 ⋅ ψ k .(74)Они показывают, что погрешность решения z k стремится к нулю тогда и толькотогда, когда стремится к нулю невязка ψ k . Этот результат позволяет судить осходимости или расходимости итерационного процесса по поведению невязки,которая доступна прямому вычислению и благодаря этому может контролироваться.При исследовании сходимости итерационных методов большую роль играютсвойства матриц A и Bn+1 , в первую очередь такие как самосопряженность изнакоопределенность.
Напомним, что в вещественном евклидовом пространстве Enдля каждого линейного преобразования существует единственное сопряженное к немулинейное преобразование, определяемое тождественным равенством скалярныхпроизведений:( Ax, y ) = (x, A*y ) , ∀x, y ∈ En .(75)В частности,( Ax, x) = (x, A*x) , ∀x ∈ En .Преобразование называется самосопряженным, если( Ax, y ) = (x, Ay ) , ∀x, y ∈ En .(76)Матрицы сопряженных преобразований в ортонормированном базисе связаныпростым транспонированием:aij* = a ji , ∀i, j = 1,K, n .Свойство самосопряженности преобразования равносильно в этом случае выполнениюусловия совпадения матриц A и A∗ :aij = a ji = aij* , ∀i, j = 1,K, n ,Как известно, любая матрица представима в виде:A = A + A% ,(77)гдеA + A*A − A**%A== A , A== − A% * .(78)22Нетрудно видеть, что- 18 -( Ax, x ) = ( A*x, x ) = ( Ax, x ) ,()A% x, x = 0.(79)В дальнейшем мы будем опираться на следующие важные свойствасамосопряженных преобразований:а) все собственные значения самосопряженного линейного преобразования(характеристические числа матрицы A ) вещественны;б) самосопряженное линейное преобразование всегда имеет полный наборлинейно независимых собственных векторов, из которых можно образоватьортонормированный базис пространства En .
В этом базисе матрица линейногопреобразования принимает диагональный вид, причем на диагонали стоят всесобственные значения этого преобразования с учетом их кратности.Наконец, матрица линейного преобразования A называется положительноопределенной, если для любого, отличного от нуля x ∈ En :( Ax, x ) > 0 ,n∑a x xi , j =1ij ij> 0 , ∀x ∈ En , x ≠ 0 .(80)Для краткости, если это не вызывает недоразумений, будем часто писать A > 0 .Необходимым и достаточным условием положительной определенностисамосопряженной матрицы A является критерий Сильвестра, из которого в частностиследует строгая положительность всех диагональных элементов:ai ,i > 0 , 1 ≤ i ≤ n .(81)Условимся обозначать собственные векторы линейного преобразования сматрицей A как ei , её характеристические числа как λi , координаты произвольноговектора x в ортонормированном базисе из собственных векторов ei как ξi .Для дальнейшего рассмотрения будут полезны три леммы.Лемма 1.Для того, чтобы симметричная ( A = A* ) матрица была положительно определенной,необходимо и достаточно, чтобы все её характеристические числа былиположительны: λi > 0 .Необходимость.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
