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

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

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

Обусловленность систем линейных уравненийДве на первый взгляд похожие системы линейных уравнений могутобладать различной чувствительностью к погрешностям заданиявходных данных. Это свойство связано с понятием обусловленности системы уравнений.Числом обусловленности линейного оператора A, дейст59вующего в нормированном пространстве R m , а также числомобусловленности системы линейных уравнений Ax = f назовемвеличину ( A )  || A ||  || A 1 || .Таким образом, появляется связь числа обусловленности с выбором нормы.Предположим, что матрица и правая часть системы заданынеточно. При этом погрешность матрицы составляет A, а правой части — f. Можно показать, что для погрешности x имеетместо следующая оценка ( || A 1 ||  || A ||  1 ):|| x |||| x ||μ( A )1  μ( A)|| δA || || A || || f || .|| f ||  || A |||| A ||В частности, если A = 0, то|| x |||| x || ( A)|| f |||| f ||.При этом решение уравнения Ax = f не при всех f одинаковочувствительно к возмущению f правой части.Свойства числа обусловленности линейного оператора:1.

( A) max || Ax ||min || Ax ||,причем максимум и минимум берутся для всех таких x, что|| x ||  1. Как следствие,2. ( A)  1.3 ( A) |  max ||  min |,где  max и  min — соответственно минимальное и максимальное по модулю собственные значения матрицы A. Равенство достигается для самосопряженных матриц в случае использования евклидовой нормы в пространстве R m .4. ( AB)  ( A)(B).Матрицы с большим числом обусловленности (ориентиро60вочно  ( A )  10 3 ) называются плохо обусловленными матрицами. При численном решении систем с плохо обусловленнымиматрицами возможно сильное накопление погрешностей, чтоследует из оценки для погрешности x.

Исследуем вопрос о погрешности решения, вызванной ошибками округления в ЭВМ привычислении правой части. Пусть t — двоичная разрядность чиселв ЭВМ. Каждая компонента f i вектора правой части округляетсяс относительной погрешностью O(2 t ). Следовательно,|| x |||| x || ( A) O(2 t ).Таким образом, погрешность решения, вызванная погрешностями округления, может быть недопустимо большой в случае плохо обусловленных систем.4.3.

Метод ГауссаМетод Гаусса является прямым методом. Запишем систему линейных уравнений в виде:a11x1  a12 x2    a1m xm  f1,a 21 x1  a 22 x 2    a 2m x m  f 2 ,.......................................................am1x1  am 2 x2    amm xm  f m .(4.1а)Пусть a11  0.

Выполнения этого условия всегда можно добиться перенумерацией компонент вектора x, либо перестановками уравнений. Тогда запишем первое из уравнений (4.1а) ввидеx1 a12a11x2   a1ma11xm f1a11.(4.2)Вычтем это уравнение, умноженное на соответствующий коэффициент ai1, из i-го уравнения системы (4.1а), где i > 1.

Тогдаэти уравнения преобразуются к виду x 2  a 23 x 3    a 2 m x m  f 2 ,a 22....................................................... 2 x2  am3 x3    amm xm  f m .am(4.3)61Первая компонента вектора x не входит в подсистему (4.3).Выполним с (4.3) те же операции, что и ранее с системой уравнений (4.1а).

В результате получим новую подсистему уравнений, в которую уже не будут входить x1 и x2 . Она дополняетсяуравнением (4.2) и первым уравнением системы (4.3), не содержащим x1. Уже после m – 3 подобных циклов мы получаем подсистему из одного уравнения с одним неизвестным. При этомматрица системы будет иметь треугольный вид. Совокупностьопераций по приведению системы уравнений к такому виду называется прямым ходом метода Гаусса.

Решение системы с треугольной матрицей не вызывает затруднений. Совокупностьопераций по нахождению решения системы с треугольной матрицей называется обратным ходом метода Гаусса.Общее число арифметических операций при решении системы (4.1а) методом Гаусса составляет O( m 3 ).В приложениях матрица A часто имеет трехдиагональныйвид, т.

е. ненулевые элементы матрицы располагаются на главнойдиагонали и двух близлежащих к ней. Применение метода Гауссак такой системе уравнений называется методом прогонки.Метод Гаусса может оказаться неустойчивым по отношению к росту вычислительной погрешности.Т еор ем а 1. Для устойчивости метода Гаусса достаточно диагонального преобладания, т. е. выполнения неравенств| aii |  | ai1 |  | ai 2 |    | aii 1 |  | aii 1 |    | aim | , > 0, i = 1, 2, …, m.Вычислительную погрешность метода Гаусса можно уменьшить, если применить модификацию метода, называемую методом Гаусса с выделением главного элемента. Суть этой модификации заключается в следующем.

Нумерация компонент вектораx и уравнений выбирается так, чтобы a11 являлся максимальнымпо модулю элементом матрицы A. Затем, после исключения x1,перенумерацией строк и столбцов добиваются того, чтобы a22 в(4.3) являлся максимальным по модулю элементом матрицы системы (4.3). Подобная процедура продолжается и далее.При расчете на реальной ЭВМ с заданным числом разрядов, наряду с влиянием неточного задания входных данных накаждой арифметической операции, вносятся ошибки округления. Влияние последних на результат зависит не только от раз62рядности машины, но и от числа обусловленности матрицы системы, а также от выбранного алгоритма. Существуют алгоритмы, учитывающие влияние ошибок округления и позволяющиеполучить результат с гарантированной точностью, если системане обусловлена настолько плохо, что при расчете с заданнойразрядностью эта точность не может быть гарантирована.4.4.

Метод сопряженных градиентовПусть матрица A системы (4.1) самосопряженная и положительно-определенная:A  A *  0.Запись A > 0 означает, что для любого x  R m , такого что|| x ||  0, выполнено( Ax, x)   ( x, x ),где  > 0.Метод сопряженных градиентов может применяться и какпрямой, и как итерационный. Итерационный метод не уступаетпо скорости сходимости методу Чебышева, который будет рассмотрен ниже, но выгодно отличается от последнего тем, что нетребует знания границ спектра. В то же время, метод сопряженных градиентов уступает методу Чебышева, поскольку являетсянеустойчивым для плохо обусловленных матриц высокой размерности. В точной арифметике этот метод дает точное решение не позднее p итераций, где p — число различных собственных значений.

Наиболее благоприятная ситуация для применения метода сопряженных градиентов имеет место, если границыспектра неизвестны, а порядок m системы много больше числаитераций k, при котором погрешность на k-й итерации  k удовлетворяет поставленному требованию точности.Метод сопряженных градиентов можно рассматриватькак модифицированный вариант метода наискорейшего спуска (см. ниже).Рассмотрим квадратичную формуВ настоящее время существуют модификации метода сопряженныхградиентов, для которых повышается скорость сходимости, и улучшается устойчивость, — см.

[6].63F ( x) 12(x, Ax)  (f , x).ПосколькуF ( x)  F ( x ) 12(x  x, A (x  x)),где x  A 1 f — решение системы (4.1), и A  A*  0, то решение задачи (4.1) эквивалентно минимизации F (x). Для градиента F (x ) справедливо выражение F ( x)  f  Ax  r.В этом направлении функционал F (x ) обладает наибольшеймгновенной скоростью изменения.Для метода сопряженных градиентов следующее приближение к решению выбирается по формулеx k 1  x k   k p k ,где p k — «вектор направления». Параметр  k выбирается таким образом, чтобы вектор p k был A-сопряженным с векторомp k 1 : (p k , Ap k 1 )  0, а значение  k вычисляется из условияминимума F ( x k 1 ) :k (p k , r k )(p k , Ap k ).Вычислительный алгоритм состоит в следующем.

Зададимпроизвольный вектор x 0  R m и построим последовательностьx1  ( E  1A ) x 0  1f ,(4.4)x k 1   k 1(E   k 1A ) x k  (1   k 1 ) x k 1   k 1 k 1f ,где k 1 1 1,64( rk , rk )( Ark , rk ),rk  Ax k  f ,k = 0, 1, 2, …, (4.5) (rk , rk )1  k 1  1  k 1 k ( Ark 1 , rk 1 )  k 1,k = 1, 2, …Оказывается, что существует номер k 0 , k 0  m, такой, что членx k0 последовательности (4.4) совпадает с точным решением x:x  x k0 ,k0  m.(4.6)Элементы последовательности x1, x 2 , …, x n являютсяуточняющимися с ростом номера k приближениями к решению;при заданном малом ,  > 0, погрешность || x  x k || приближения x k при некоторых условиях может стать меньше  даже призначениях k << m.Можно показать, что «вектор направления» p k с точностью до скалярного множителя представляет собой проекциюградиента r k   F ( x k )  f  Ax k на пространство, натянутоена векторы p k , p k 1 , …, p N 1 , а векторы p 0 , …, p N 1 являются взаимно A-сопряженными.

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

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