Главная  Методы условной оптимизации 

[0] [1] [2] [3] [4] [5] [6] [ 7 ] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83]

И соответственно

11бд:<Л-м1 цели \\х+Ы\,

или, что то же самое.

II х+бх II

IIЛ-Ч1 6Л.

Вводя относительное возмущение матрицы, это неравенство можно переписать так:

<1Л11Л-М]1. (2.29)

И в (2.28), и в (2.29) верхней границей относительного изменения точного решения служит произведение порождающего его относительного возмущения данных (правой части или матрицы) на одно н го же число 1Л Л"Ч. Это число называют числом обусловленности матрицы А в процедуре решения линейной системы (указание на процедуру обычно опускается) и обозначают через сопй(А).

Поскольку для любой подчиненной матричной нормы выполняется равенство 11/11 = 1 и по определению /=Л~М, справедлива оценка

1 = 1Л1<11Л11Л-Ч1,

так что соп(1(Л)>1 для любой матрицы.

Число обусловленности матрицы Л характеризует максимальный эффект от возмущений в Ь и Л при решении (2.25). Из оценок (2.28) и (2.29) следует, что при «большом» сопи (А) точное решение системы может существенно изменяться даже при малом изменении данных. Матрицы Л с «большими» соп(1(Л) принято называть плохо обусловленными, а с «малыми» cond (Л) - хорошо обусловленными.

Чтобы проиллюстрировать сказанное, рассмотрим систему с матрицей Л и правой частью b вида

/.550 .423\ /-127\

=(,.484 .372J- " = 1112/ Точное решение уравнения Лх=Ь есть

(2.30)

При возмущенной правой части Ы-6Ь =

Л12707\

ЬЬ-.

.00028J

точным решением становится вектор

+«=(-I:9i) "={-1)-

В данном случае в норме Н „ получим 6Ь/Ь = .0О22, в то время как 6д:1/д: = .91. Видно, что относительное изменение решения намного превышает отьюсительное изменение правой части.

Проварьируем теперь (2, 1)-й элемент матрицы Л так, чтобы .530 . 4234

Л--6Л =

.483

.4234 .372/

При этом точное решение возмущенной системы

(А+ЁА) (x+tx)=b,

округленное до четырех знаков, выглядит следующим образом:

/-.4535\ + « = V .8899>

И здесь относительное изменение решения намного превышает относительное изменение исходных данных (матрицы Л). Объяснение в обоих случаях одно и то же - плохая обусловленность матрицы из (2.30). Обратная к ней матрица А~ (с точностью до четырех знаков) имеет вид

-2818 3667

3205\ -4167/

и соответственно в норме И-П., будет 1Л = .973, Л~Ч=7834, соп(1(Л)=7622. Таким образом, неожиданно большие на первый взгляд вариации решения еще очень далеки от тех, которые могли бы получиться в худшем случае.

Следует подчеркнуть, что представленный анализ возмущений проводился в терминах точных решений и, значит, касался только внутренних свойств рассмотренной математической задачи. Плохая обусловленность была определена безотносительно к проблемам вычислений с конечной точностью и по сути дела представляет собой чисто геометрическую характеристику матричного преобразования. Она говорит о том, что коэффициенты растяжения разных векторов преобразованием Л сильно разбросаны.

2.2.4.4. Треугольные линейные системы. Рассмотрим задачу численного поиска решения невырожденной линейной системы вида

Ах=Ь.

(2.31)

В каких случаях это решение может быть получено простой процедурой? Предположим, что матрица Л является треугольной (скажем, нижней треугольной). Так что система (2.31) на самом деле



ВЫГЛЯДИТ так:

(31 и

. („1 и („3 . . Inr. \ "г.

В данном случае первое уравнение содержит единственную неизвестную Ai, значение которой сразу определяется посредством одного деления:

In

Во второе уравнение входят две искомые величины xt и Xj, но первая нам уже известна, и поэтому этого уравнения достаточно, чтобы найти вторую. Она вычисляется по формуле

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

Процедура, аналогичная рассмотренной, может быть использована и для поиска решения системы с верхней треугольной матрицей, только тогда надо вычислить сначала х„, затем д:„ 1 и т. д. Ее называют подстановкой назад, а процедуру решения нижней треугольной системы - подстановкой вперед.

Количество арифметических операций, необходимых для решения треугольной системы общего вида описанным способом, оценивается так: для вычисления первой неизвестной нужно одно деление; расчет второй неизвестной включает одно умножение, одно сложение и одно деление; при вычислении к-й неизвестной потребуется выполнить к-1 сложений, к-1 умножений и одно деление и т. д. вплоть до к=п. Просуммировав все это, получим, что полное число сложений и полное число умножений равны "/п", а полное число делений равно п.

Еще проще решаются системы (2.31) с диагональной матрицей А (которую можно рассматривать как особую разновидность треугольной). В этом случае каждое уравнение содержит в точности одну неизвестную, значение которой никак не связано со значе-

ниями других неизвестных. Для решения диагональной линейной системы нужно выполнить только п делений и ничего больше,

I 2.2.4.5. Анализ ошибок. Выше (разд. 2,1,7) было введено по-гнятие обратного анализа ошибок - подхода, который применительно к любой вычислительной процедуре состоит в интерпретации численного решения исходной задачи как точного решения некоторой возмущенной задачи и в оценке близости между этими задачами Такой анализ очень важен для понимания численных алгоритмов, но, к сожалению, его детали всегда ужасно утомительны. Поэтому стандартная техника будет проиллюстрирована на весьма кратка изложенной процедуре обратного анализа ошибок для алгоритма решения нижней треугольной системы линейных уравнений подстановкой вперед. При этом будут использованы сведения о вычислениях с плавающей запятой, данные в разд. 2.1.4, Первый шаг решения системы Lx=b, где L - нижняя треугольная матрица, состоит в расчете первой компоненты вектора неизвестных. Ее численно найденное значение будет равно

где величина 6il ограничена сверху малым числом Ем, отражающим точность машинных вычислений. Следовательно, Xi окажется точным решением уравнения

(ii(l+6i)Xi=bi. Далее, расчетным значением второй компоненты х будет

x, = fl (

1г, (I Н-бг)

(2.33)

где 21, г]зг, 6g обусловлены погрешностями умножения, сложения и деления соответственно. Модуль каждой из этих величин ограничен сверху константой Ед,. После объединения слагаемых, связанных с разными ошибками, (2.33) можно переписать так:

i2,(l + Pgi)xi+/gg(l+Pgg)A:g=bg,

Здесь iPail и iPasI нб превосходят произведения некоторого фиксированного числа на Ед,.

Продолжая эти рассуждения, нетрудаю убедиться, что расчетное значение х,, найденное на г-м шаге, будет удовлетворять уравнению

;ri(l+P,i)A:,-f(.g(l-fP„)Xg+, , ,+(„(1+РЖ=Ь„

где каждая из величин ipl ограничена сверху произведением е на некоторую линейную функцию от номера итерации г. Таким Образом, показано, что численное решение х является точным



решением возмущенной треугольной системы вида

(2.34)

в которой модуль каждого элемента г-й строки матрицы 6Z. не превосходит выражения, содержащего машинную точность, номер г и соответствующий элемент исходной матрицы L. Значит, хотя истинное возмущение HL, возникающее при конкретной правой части Ь, является функцией генерируемого численного решения, оценки для \(ЬЦи\ сверху не зависят ни от Ь, ни от х, ни от числа обусловленности матрицы L. Равенство (2.34) в силу этих оценок означает, что численное решение исходной системы оказывается точным решением системы, близкой к ней.

2.2.5. РАЗЛОЖЕНИЯ МАТРИЦ

Во многих задачах вычислительной линейной алгебры оказывается полезным представлять исходные матрицы произведениями или суммами других матриц специального вида. Такие представления называют разлоокениями или факторизациями.

Несколько разложений, наиболее часто употребляемых в оптимизационных алгоритмах, будут более или менее подробно рассмотрены в данном разделе.

2.2.5.1. /.-разложение; гауссовы исключения. Один из подходов к решению невырожденной линейной системы общего вида

Лл=Ь (2.35)

состоит в преобразовании ее в эквивалентную систему с треугольной матрицей. Для этого надо построить такую невырожденную матр1щу М, чтобы произведение МА было треугольным. Затем можно искать х как решение эквивалентной (2.35) системы вида МАх=МЬ методом подстановки вперед или назад Интересно отметить, что наиболее часто употребляемая формальная процедура построения М в значительной степени совпадает с известной всем со школьной скамьи процедурой решения небольших систем линейных алгебраических уравнений с помощью карандаша и бумаги.

Рассмотрим линейную систему

2х, + 2х,+ х, = 5,

Xi + 3x, + 2x, = e, (2.36)

ix,-2x, + 3x,=5.

у которой

-2 3

(2.37)

В качестве первого шага ее решения «исключим» переменную Xi из второго и третьего уравнений, вычитая из второй строки матрицы системы первую, поделенную на 2, а из третьей - первую, умноженную на 2. В результате придем к матрице с нулями во (2, 1)-й и (3, 1)-й позициях. Полностью она будет выглядеть так:

2 2 \

Л" =

О 2 3/2

v0 -6 I у

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

/2 2 2 \

Л"> = ( 0 2 3/2 . \0 О П/2/

Изложенный способ последовательной триангуляризации матрицы поочередным обнулением поддиагональных элементов называется гауссовыми исключениями. После выполнения k-1-го шага этой процедуры первые ft-1 столбцов матрицы системы уже преобразованы к верхнему треугольному виду, и значения их компонент в дальнейшем не изменяются. На k-u шаге исключения обнуляют все (/, k)-e элементы с j>k, для чего k-я строка поочередно вычитается из /-х с весами т, где

Диагональный элемент 0$, частично преобразованной матрицы называется ведущим элементом k-ro шага. Он имеет особое значение, так как, если на каком-то шаге окажется нулевым, вычисления придется прервать. Числа {mh}. /=fe+l, . . ., п, называют множите.1ями k-ro шага.

После того как матрица преобразована в верхнюю треугольную, все действия, совершенные по ходу этого преобразования с ее строками, надо проделать с компонентами правой части. Тем самым построение треугольной системы, эквивалентной исходаюй, будет завершено, и останется только одно - найти ее решение методом подстановки назад. В примере (2.36) вектор b трансформируется следующим образом:

/5\ / 5 \

7/2 -5/

11/2/

а метод подстановки назад дает а-,= 1, х,= \, jCi=1.



[0] [1] [2] [3] [4] [5] [6] [ 7 ] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83]

0.0009