МУ к лабораторным работам (1238837), страница 10

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

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

Отсюда следует название метода — «сопряженных градиентов».В настоящее время метод сопряженных градиентов при«умеренном» числе обусловленности и больших m используетсяобычно именно как метод последовательных приближений.Попытка вычисления точного решения при большом числеобусловленности и большом m с помощью последовательности(4.4) и с учетом равенства (4.6) может натолкнуться на препятствие, состоящее в возможной потере вычислительной устойчивости при нахождении членов x k последовательности (4.4).Заметим, что для применения метода не обязательно, чтобы система была задана в каноническом виде  aij x j  f i ,i = 1, 2, …, m, или приведена к такому виду. К тому же нет необходимости хранить матрицу A, которая имела бы m 2 элементов, в то время как векторы y  R m и z  Ay  R m , записанныев координатной форме, задаются лишь m числами каждый.4.5.

Метод простых итерацийЗаметим, что систему линейных уравнений65Ax  fможно преобразовать к виду(4.7)x  (E  A) x  f ,(4.8)причем новое уравнение (4.8) равносильно исходному при любом значении . Вообще, (4.7) многими способами можно заменить равносильной системой видаx  B x  ,x  Rm,  Rm,(4.9)частным случаем которой является (4.8).Итерационная схема при заданном произвольно x 0 имеетследующий видx p 1  Bx p  ,p = 0, 1, …(4.10)при заданном произвольно x 0 .Ниже приведены условия, при которых последовательность(4.10) сходится к решению системы (4.7).Рассмотрим частный случай итерационной формулы (4.10):x p 1  (E  A ) x p  f ,p = 0, 1, …(4.11)Для вычисления по этой формуле достаточно уметь по заданному x p  R m находить элемент Ax p , получающийся в результате действия оператора A.Таким образом, итерационный процесс вычисления решения системы Ax = f, в отличие от метода Гаусса, можно реализовать и в случае операторной формы задания системы линейных уравнений, не выделяя какой-либо базис в R m и не приводя к каноническому видуm aij x j  f i ,i = 1, 2, …, m.(4.12)j 1Для некоторых классов систем линейных уравнений числоарифметических действий, необходимых для получения решения с разумной точностью итерационными методами многоменьше, чем O ( m 3 ).Т еор ем а 2.

(Достаточное условие сходимости). Пусть вR m фиксирована некоторая норма, причем соответствующая66норма оператора B равносильной системы (4.9) оказаласьменьше единицы:|| B ||  q  1.(4.13)Тогда система (4.7) имеет одно и только одно решение x;при любом x 0 из R m последовательность (4.10) сходится крешению x, причем погрешность p-го приближения (или p-йитерации)εp xxpудовлетворяет оценке|| ε p ||  q p || ε 0 || .(4.14)Тем самым, норма погрешности || ε p || стремится к нулю сростом p не медленнее геометрической прогрессии q p .За м еча ние. Условие (4.13) может нарушаться при какомнибудь другом выборе нормы || x || .

Однако сходимость сохранится, причем оценка (4.14) заменится оценкой|| ε p || Cq p || ε 0 ||,где C — некоторая постоянная, зависящая от новой нормы, азнаменатель прогрессии q — прежний.Т еор ем а 3. (Необходимое и достаточное условие сходимости). Для того, чтобы итерационный процесс (4.10) сходился при любом начальном приближении, необходимо и достаточно, чтобы все собственные значения B лежали внутриединичного круга.За м еча ние. В условиях теоремы при проведении вычислений вреальной арифметике (с ограниченным числом значащих цифр)метод простых итераций может оказаться неустойчивым к ростуошибок округления. Например, если спектральный радиус матрицы B меньше единицы, а || B ||  1.

(См. пример из задания.)4.6. Метод Зейделя и метод релаксацииИтерационная схема имеет видBx n 1  Cx n  f .67Здесь B — треугольная матрица, содержащая выше главной диагонали нули, а на главной диагонали и ниже ее — элементы матрицы A:C  A  B.Т еор ем а 4. (Достаточное условие сходимости). Пусть A —вещественная симметричная положительно определенная матрица. Тогда метод сходится при любом начальном приближении.Если для отыскания следующего приближения используетсяитерационная схема вида( B  D ) x n 1 1D ( x n 1  (1  )x n )  Cx n  f ,где D — диагональная матрица с элементами aii на главнойдиагонали, то такой метод называется методом релаксации.В случае   1 метод называется методом верхней релаксации.

Обычно полагают 1    2. Очевидно, что в случае  1 метод релаксации совпадает с методом Зейделя.4.7. Метод простых итерацийс оптимальным параметромПусть матрица А в (4.1) самосопряженная и положительно-определенная: A  A*  0. Собственные числа  в этом случае действительные положительные числа.Пусть известны наименьшее  min и наибольшее  maxсобственные значения A. Зададим произвольное приближениеx 0 и рассмотрим последовательность простых итераций:x p 1  (E  A ) x p  f ,p = 0, 1, …Справедлива следующая теорема.Т еор ем а 5.

1) Если  достаточно мало, а именно, удовлетворяет неравенствам02 max,(4.15)то последовательность x p сходится к решению x системыуравнений Ax = f, причем гарантировано убывание нормы по-68грешности || x  x p || при возрастании p в соответствии с оценкой|| ε p ||  q p || ε 0 ||,p = 0, 1, …(4.16)Здесь q < 1 и дается выражением:q  q ()  max {| 1   min |, | 1   max |},(4.17)т. е.

q — наибольшее из чисел | 1   min | и | 1   max |, каждое из которых при условии (4.15) строго меньше единицы.2) Пусть  — произвольное число, удовлетворяющее (4.15).Существует начальное приближение x 0 , при котором оценку(4.16) улучшить нельзя, так как соотношение (4.16) превращается в точное равенство.3) Если условие (4.15) не выполняется, то существует x 0 ,при котором последовательность x p не сходится с ростом p крешению x.4) Значение    опт , при котором q, задаваемое формулой(4.17), принимает наименьшее значение qопт  q(опт ), есть   опт 2 min   max.В этом случае q принимает наименьшее значениеq  qопт ( A )  1( A )  1,где (A)   max /  min — число обусловленности оператора A.За м еча ние 1. Во многих случаях (например, при приближенной замене некоторых эллиптических краевых задач разностными) оператор A оказывается положительно определенным исамосопряженным в смысле некоторого естественного скалярного умножения.

Однако обычно не удается точно указать егоТакой вариант метода простых итераций часто называют методомпростых итераций с оптимальным параметром.Отметим, что ( A )   max /  min верно для самосопряженной матрицы, если в R m выбрана норма вектора || x ||  (x , x ) .69наибольшее и наименьшее собственные значения. Можно указать лишь общие оценки границ спектра, т. е.

числа a и b такие,что выполняются неравенства0  a   min   max  b.В этом случае также можно воспользоваться методом простых итераций. Сходимость окажется тем медленнее, чем хужеизвестны границы спектра a и b.За м еча ние 2. Чем больше число обусловленности матрицы A,тем больше значение q опт и тем хуже скорость сходимости. В некоторых случаях сходимость метода простых итераций для плохообусловленных систем уравнений можно существенно улучшить.4.7.1.

Переход к лучше обусловленной системе с помощьюэнергетически эквивалентного оператора. В случае плохо обусловленной системы Ax = f иногда удается перейти к равносильной системе с оператором, который имеет меньшее число обусловленности, а затем решить эту систему методом итераций.Пусть B  B*  0 — пока произвольный оператор. Умножим обе части уравнения Ax = f на B 1. В результате получимравносильное уравнениеCx  g,C  B 1A,g  B 1f .Оператор C является самосопряженным и положительно определенным в смысле скалярного произведения (x, y )B  (Bx, y ).Имеет смысл выбирать оператор B лишь среди тех операторов,для которых вычисление B 1z по заданному z существеннопроще, чем вычисление A 1z.

Если при этом удается выбрать Bтак, чтобы он был «похож» на оператор A, то можно надеяться,что оператор B 1A будет «похож» на единичный, а его максимальное и минимальное собственные числа и число обусловленности будут «ближе» к единице.4.7.2. Масштабирование как средство улучшения числа обусловленности. Прием масштабирования заключается в следующем. Каждое из скалярных уравнений системы умножаетсяна такой множитель, чтобы максимальный коэффициент новогоуравнения оказался равным единице.

От этой новой, масштабированной системы уравнений вида A x  f , переходим к равно70сильной системе с симметричной и положительно определеннойматрицей путем умножения обеих частей системы на (A)* .4.8. Трехслойный метод ЧебышеваПусть A  A *  0, а также известны числа a > 0 и b > 0, являющиеся границами спектра оператора A.

Зададим произвольноенулевое приближение x 0 и будем вычислять последующие приближения по формулам:x1  E   A  x 0   f ,x p 1 21 p p 1где p = 1, 2, …;   0  1,( E  A) x p 1 2a b1 1  p 1 p 1x p 1 21 p p 1f,,  k   k (),   a / b заданы как:, p 1  2 1 p   p 1,p = 1, 2, …Можно показать, что погрешность ε p  x  x p приближенияx p удовлетворяет оценке|| ε p ||   a / b,2q p1 q2p|| ε 0 ||,q1 ,1 p = 1, 2, …Метод сходится тем быстрее, чем точнее определены границыспектра a и b.Рассмотренный метод часто называют трехслойным методом Чебышева в отличие от двухслойного метода Чебышева(см.

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

Список файлов книги