Методы вычислений. Часть I. Численные методы алгебры: Учебное пособие

Курцева Кира Петровна, Шешуков Евгений Геннадьевич.

Методы вычислений. Часть I. Численные методы алгебры. Конспекты лекций и задачи.

1

УДК 519.6

Методы вычислений. Часть I. Численные методы алгебры. / ЗФ КГУ; Сост.: Курцева К.П., Шешуков Е.Г.; Зеленодольск, 2007. – 70c. Учебное пособие содержит основные приемы численного решения систем линейных алгебраических уравнений, вычисление определителей, обращение матриц, нахождение собственных чисел и собственных векторов матрицы. Дополнительно рассматриваются и некоторые методы решения нелинейных уравнений и систем нелинейных уравнений. Приводятся примеры решения типовых задач и упражнения для самостоятельной работы.

2

ОГЛАВЛЕНИЕ Введение...............................................................................................................4 I. Численные методы решения систем линейных алгебраических уравнений (СЛАУ) ...................................5 1. Точные (прямые) методы ...............................................................................5 Методы исключения неизвестных.....................................................................5 Методы, основанные на разложении матрицы коэффициентов...................13 2. Приближенные методы.................................................................................20 Метод простой итерации ..................................................................................20 Метод Зейделя ...................................................................................................27 Метод релаксации .............................................................................................31 II. Вычисление определителей, обращение матриц.....................................32 1. Вычисление определителей ........................................................................32 2. Вычисление элементов обратной матрицы. ...............................................34 III. Проблема собственных чисел ....................................................................36 1. Решение полной проблемы собственных чисел. Прямые методы. ..........36 2. Частичная проблема собственных чисел ...................................................46 IV. Методы решения нелинейных алгебраических уравнений ....................49 1. Случай одного уравнения. Исследование уравнения ................................49 2. Итерационные методы вычисления изолированного корня уравнения f ( x) = 0 ..................................................60 3. Метод простой итерации для системы двух уравнений............................62 4. Итерационные методы для системы с n нелинейными уравнениями .....65

3

Введение. Под численным методом понимается такая интерпретация математической модели, которая доступна для реализации на ЭВМ. В настоящее время численные методы являются мощным математическим средством решения многих научнотехнических задач. Это связано как с невозможностью в большинстве случаев получить точное аналитическое решение, так и со стремительным развитием компьютерной техники. Процесс исследования исходного объекта методом математического моделирования и вычислительного эксперимента неизбежно носит приближенный характер, так как на каждом этапе вносятся те или иные погрешности. 1. Источники и классификация погрешностей. Существует четыре источника погрешностей, полученных в результате численного решения: физическая и математическая модели, исходные данные, приближенность метода и ошибки округления. двум источникам называется Погрешность, соответствующая первым неустранимой. Погрешность метода связана со способом решения поставленной математической задачи и появляется в результате подмены исходной математической модели другой или конечной последовательностью других моделей. Погрешность округления возникает в связи с тем, что вычисления проводятся с конечным числом значащих цифр. Все описанные типы погрешностей в сумме дают полную погрешность результата решения задачи. 2. Абсолютная и относительная погрешность приближенных значений.

a∗ – приближенное значение точной величины a . Абсолютной ∗ ∗ погрешностью приближенного значения a называют такое число Δ ( a ) , для Пусть

которого справедливо неравенство

a∗ − a ≤ Δ ( a∗ ) *

Относительной погрешностью приближенного значения a называют такое число δ (a* ) , для которого справедливо неравенство

a∗ − a a∗

≤ δ ( a∗ )

Относительную погрешность часто выражают в процентах. 3. Значащие цифры. Верные цифры (знаки) приближенного числа. Значащими цифрами числа называют все цифры в его записи, начиная с первой ∗

∗

ненулевой слева, например, у чисел a = 0,01023 , a = 0,01023000 значащими цифрами являются подчеркнутые цифры. Первое число имеет четыре значащие цифры , второе – семь значащих цифр. Значащую цифру называют верной, если абсолютная погрешность числа не превосходит единицы разряда, соответствующего этой цифре. Например, при

a∗ = 0,01023 , Δ(a∗ ) = 0,000004 ; a∗ = 0,01023000 , Δ(a∗ ) = 0,0000006 .

Сомнительными называют все цифры приближенного числа, расположенные правее последней верной цифры.

4

I. Численные методы решения систем линейных алгебраических уравнений (СЛАУ). Система m линейных уравнений с n неизвестными имеет вид:

⎧a11x1 + a12 x2 + K + a1n xn = b1, ⎪a x + a x + K + a x = b , ⎪ 21 1 22 2 2n n 2 ⎨ ⎪KKKKKKKKKKKK ⎪⎩am1x1 + am 2 x2 + K + amn xn = bm , где

aij , bi (i = 1,2,..., m; j = 1, 2,..., n)

–

произвольные

(1)

числа,

называемые

соответственно коэффициентами при переменных и свободными членами уравнений. Система уравнений называется совместной, если она имеет хотя бы одно решение, и несовместной, если она не имеет решений. 1. Точные (прямые) методы. Метод называется точным, если при точном выполнении всех требуемых действий мы получаем точное решение системы. При этом имеется в виду, что все коэффициенты – точные числа. Методы исключения неизвестных 1.1 Метод Гаусса. Наиболее распространенным методом решения СЛАУ является метод Гаусса, в основе которого лежит идея последовательного исключения неизвестных. С помощью элементарных преобразований система уравнений приводится к равносильной системе ступенчатого (или треугольного) вида, из которой последовательно, начиная с последних (по номеру) переменных, находятся все остальные переменные. Рассмотрим решение системы (1) m линейных уравнений с n неизвестными в общем виде. Предположим, что в системе (1) a11 ≠ 0 (этого всегда можно добиться перестановкой уравнений или переменных с изменением их номеров). Шаг 1. Умножая первое уравнение на подходящие числа (а именно на −a21 a11 , − a31 a11 ,..., − am1 a11 ) и прибавляя полученные уравнения соответственно ко второму, третьему,…, m -му уравнению системы (1), исключим переменную x1 из всех последующих уравнений, начиная со второго. Получим

⎧a11x1 + a12 x2 + K + a1n xn = b1, ⎪ (1) a22 x2 + K + a2(1)n xn = b2(1) , ⎪ ⎨ ⎪.................................................. (1) ⎪ am(1)2 x2 + K + amn xn = bm(1) , ⎩

(2)

где буквами с верхним индексом (1) обозначены новые коэффициенты, полученные после первого шага. (1)

Шаг 2. Предположим, что a22 ≠ 0 . Умножая второе уравнение из (2) на числа (1) (1) (1) (1) (1) −a32 a22 , −a42 a22 ,..., −am(1)2 a22

и прибавляя полученные уравнения соответственно к третьему, четвертому, …, m -му уравнению системы (2), исключим переменную x2 из всех последующих уравнений, начиная с третьего. Продолжая процесс последовательного исключения переменных x3 , x4 ,K, xr −1 , после ( r − 1 ) шага получим систему 5

⎧a11x1 + a12 x2 + K + a1r xr + a1,r +1xr +1 + ... + a1n xn = b1, ⎪ (1) a22 x2 + K + a2(1)r xr + a2,(1)r +1xr +1 + ... + a2(1)n xn = b2(1) , ⎪ ⎪ ⎪.......................................................................................... ( r −1) ⎪⎪ arr( r −1) xr + ar( r,r−+1)1 xr +1 + ... + arn xn = br( r −1) , ⎨ ⎪.......................................................................................... ⎪ 0 = br(+r 1−1) , ⎪ ⎪ ............ ⎪ 0 = bm( r −1) . ⎪⎩ ( r −1)

(3)

( r −1)

Для любой совместной системы числа br +1 ,…, bm в системе (3) равны нулю, т.е. последние m − r уравнений являются тождествами, и они не влияют на решение системы (1). После отбрасывания “лишних” уравнений возможны два случая: а) число уравнений системы (1) равно числу переменных, т.е. r = n (в этом случае система (3) имеет треугольный вид); б) r < n (в этом случае система (3) имеет ступенчатый вид). Переход системы (1) к равносильной ей системе (3) составляет прямой ход метода Гаусса. Обратный ход заключается в нахождении неизвестных x1, x2 ,K, xn из системы (3) . Рассмотренная вычислительная схема, реализующая этот метод называется схемой единственного деления. Достоинства метода Гаусса: • менее трудоемкий (по сравнению с методом обратной матрицы и расчетами по формулам Крамера); • позволяет однозначно установить, совместна система или нет, а в случае совместности найти ее решения (единственное или бесконечное множество); • дает возможность найти максимальное число линейно независимых уравнений – ранг матрицы системы. Преобразования Гаусса удобно проводить не с самими уравнениями, а с расширенной матрицей системы (1). Пример. Методом Гаусса решить систему уравнений:

⎧ x1 + 2 x2 + 3 x3 − 2 x4 = 6, ⎪2 x + 4 x − 2 x − 3 x = 18, ⎪ 1 2 3 4 ⎨ ⎪3 x1 + 2 x2 − x3 − 2 x4 = 4, ⎪⎩2 x1 − 3 x2 + 2 x3 + x4 = −8 Решение. Расширенная матрица системы имеет вид:

⎛ 1 2 3 −2 6 ⎞ ⎜ ⎟ ⎜ 2 4 −2 −3 18 ⎟ . ⎜ 3 2 −1 2 4 ⎟ ⎜⎜ ⎟⎟ ⎝ 2 −3 2 1 −8 ⎠

6

Шаг 1. Так как a11 ≠ 0 , то ко второй, третьей и четвертой строкам матрицы прибавляем первую строку, умноженную соответственно на числа ( −2), (−3), (−2) и исключаем переменную x1 из всех строк, начиная со второй. В новой матрице (1) a22 = 0 , поменяем местами вторую и третью строки:

⎛1 2 3 ⎜ ⎜ 0 0 −8 ⎜ 0 −4 −10 ⎜⎜ ⎝ 0 −7 −4 (1) Шаг 2. Так как теперь a22

−2

6 ⎞ ⎛1 2 3 −2 6 ⎞ ⎟ ⎜ ⎟ 1 6 ⎟ ⎜ 0 −4 −10 8 −14 ⎟ . 8 −14 ⎟ ⎜ 0 0 −8 1 6 ⎟ ⎟ ⎜ ⎟ 5 20 ⎟⎠ ⎜⎝ 0 −7 −4 5 20 ⎟⎠ = −4 ≠ 0 , то умножая вторую строку на ( −7 4 ) и прибавляя полученную строку к четвертой, исключим переменную x2 из всех строк, начиная с третьей. (2)

Шаг 3. Учитывая, что a33 = −8 ≠ 0 , умножаем третью строку на

13,5 8 = 27 16 , и прибавляя к четвертой строке, исключим из нее переменную x3 . ⎛1 2 −2 6 ⎞ 3 ⎜ ⎟ ⎜ 0 −4 −10 8 −14 ⎟ ⎜0 0 −8 1 6 ⎟ ⎜⎜ ⎟⎟ ⎝ 0 0 13,5 9 4,5 ⎠

⎛1 2 −2 3 6 ⎞ ⎜ ⎟ −14 ⎟ 8 ⎜ 0 −4 −10 ⎜ 0 0 −8 1 6 ⎟. ⎜ ⎟ 117 117 ⎟ ⎜0 0 0 − ⎜ ⎟ 16 8 ⎠ ⎝

Получим систему уравнений

⎧ x1 + 2 x2 + 3 x3 − 2 x4 = 6, ⎪ − 4 x2 − 10 x3 + 8 x4 = −14, ⎪⎪ ⎨ − 8 x3 + x4 = 6, ⎪ 117 117 ⎪ − x4 = , ⎪⎩ 16 8

откуда, используя обратный ход метода Гаусса, найдем решение системы (1; 2; − 1; 2 ) . 3

1.2 Метод Гаусса с выбором главного элемента. ( N = O (n ) ) (i −1)

На каждом шаге при прямом методе Гаусса мы делили на элемент aii ≠0 – этот элемент назывался ведущим. Может получиться так, что элемент близок к 0, следовательно, коэффициенты в уравнении будут большими, что приведет к увеличению арифметической погрешности при обратном ходе. В этом случае удобнее применять метод Гаусса с выбором главного элемента. Основная идея метода состоит в том, что на очередном шаге исключать не следующее по номеру неизвестное, а то неизвестное, коэффициент при котором является наибольшим по модулю. Таким образом, в качестве ведущего элемента здесь выбирается главный, т.е. наибольший по модулю элемент. Например, в системе

⎧a11x1 + a12 x2 = b1, ⎨ ⎩a21x1 + a22 x2 = b2 , 7

a12 > a11 , тогда на первом шаге будем исключать переменную x2 . Такой прием эквивалентен тому, что исходная система перепишется в виде

⎧a12 x2 + a11x1 = b1, ⎨ ⎩a22 x2 + a21x1 = b2 , и к ней применяется первый шаг обычного метода Гаусса. Указанный способ исключения называется методом Гаусса с выбором главного элемента по строке. Он эквивалентен применению обычного метода Гаусса к системе, в которой на каждом шаге исключения проводится соответствующая перенумерация переменных. Применяется также метод Гаусса с выбором главного элемента по столбцу. Предположим, что a21 > a11 . Перепишем систему в виде

⎧a21x1 + a22 x2 = b2 , ⎨ ⎩a11x1 + a12 x2 = b1, и к новой системе применим на первом шаге обычный метод Гаусса. Таким образом, метод Гаусса с выбором главного элемента по столбцу эквивалентен применению обычного метода Гаусса к системе, в которой на каждом шаге исключения проводится соответствующая перенумерация уравнений. Иногда применяется метод Гаусса с выбором главного элемента по всей матрице, когда в качестве ведущего выбирается максимальный по модулю элемент среди всех элементов матрицы системы. Смысл выбора главного элемента состоит в том, чтобы сделать возможно меньшими новые коэффициенты системы и тем самым уменьшить погрешность вычислений. 3

1.3 Метод оптимального исключения ( N = O(n ) ) Прямой и обратный ход совмещены. Рассмотрим систему для случая m = n

⎧a11x1 + a12 x2 + K + a1n xn = b1, ⎪a x + a x + K + a x = b , ⎪ 21 1 22 2 2n n 2 ⎨ ⎪KKKKKKKKKKKK ⎪⎩an1x1 + an 2 x2 + K + ann xn = bn , Положим в 1-ом уравнении a11 ≠ 0 , делим на него: 1 шаг :

(1) (1) x1 + a12 x2 + K + a1(1) n xn = b1 ,

2 шаг: исключаем из второго уравнения системы неизвестную x1 получаем: (1) (1) a22 x2 + a23 x3 K + a2(1)n xn = b2(1) , (1)

Полагаем a22 ≠ 0 , делим на него второе уравнение, получаем (2) (2) x2 + a23 x3 K + a2(2) n xn = b2 ,

Затем с помощью этого уравнения исключаем x2 из первого уравнения, получаем (2) (2) x1 + K + a13 x3 + K + a1(2) n xn = b1 ,

8

3 шаг: в результате аналогичных операций из третьего уравнения получаем:

системы

(3) (3) x3 + a34 x4 + K + a3(3) n xn = y3 ,

Затем с помощью этого уравнения исключаем x3 из преобразованных первого и второго уравнений системы, получаем, что 3 первых уравнения системы имеют вид (3) (3) + a14 x4 + K + a1(3) n xn = y1 ,

x1 x2

(3) + a24 x4 + K + a2(3)n xn = y2(3) , (3) (3) x3 + a34 x4 + K + a3(3) n xn = y3 .

Остальные уравнения в системе преобразуются аналогичным образом. В этом методе экономится память, т.о. можно решать системы с числом неизвестных в два раза больше метода Гаусса. В методе оптимального исключения обратный ход метода Гаусса здесь видоизменен и соединен с прямым ходом. 1.4 Метод прогонки Это частный случай метода Гаусса с ленточной матрицей вида (М1). Применяя к такой системе метод Гаусса мы приходим к системе матрицы (М2) .

⎛× ⎜× ⎜ ⎜0 ⎜ ⎜0 ⎜0 ⎝

× × × 0 0

0 × × × 0

0 0 × × ×

0⎞ 0 ⎟⎟ 0 ⎟ (М1) ⎟ ×⎟ × ⎟⎠

⎛× ⎜0 ⎜ ⎜0 ⎜ ⎜0 ⎜0 ⎝

× × 0 0 0

0 × × 0 0

0 0 × × 0

0⎞ 0 ⎟⎟ 0⎟ ⎟ ×⎟ × ⎟⎠

(М2)

Пусть система имеет вид

⎧⎪ai xi −1 − bi xi + ci xi +1 = di , ⎨ ⎪⎩a1 = cn = 0.

i = 1, n,

(4)

Если к этой системе применить метод Гаусса, то любое уравнение будет связывать xi −1, xi , xi +1 и свободный член. В методе прогонке решение ищется в виде рекуррентного соотношения, которое следует из применимости метода Гаусса

xi = ξi +1xi +1 + ηi +1 ,

(5)

где ξi +1,ηi +1 – коэффициенты прогонки. После несложных преобразований получаем рекуррентные соотношения для коэффициентов прогонки.

ξi +1 =

ci , bi − aiξi

ηi+1 =

di − aiηi . aiξi − bi

(6)

Надо знать начальные значения коэффициентов прогонки и конечное значение xn . Эти неизвестные можно взять из неполных уравнений. Подставим a1 = 0 в (4), получим

9

−b1x1 + c1x2 = d1, c1 d x2 − 1 , b1 b1

x1 =

x1 = ξ 2 x2 + η2 . Пользуясь начальными значениями коэффициентов прогонки последовательность всех коэффициентов прогонки

ξ2 =

можно найти

c1 d , η2 = − 1 . b1 b1

Нахождение коэффициентов прогонки называется прямым ходом метода прогонки.

⎧an xn−1 − bn xn = d n , ⎨ ⎩ xn−1 − ξ n xn = η n . Отсюда найдем xn , тогда из рекуррентного соотношения найдем сами неизвестные. Это обратный ход метода прогонки Достаточным условием для устойчивости метода прогонки к накоплению арифметических ошибок является:

bi > ci + ai Пример. Даны ленточная матрица и столбец свободных членов. Требуется решить методом прогонки систему из пяти ЛАУ.

⎛2 ⎜ ⎜1 ⎜0 ⎜ ⎜0 ⎜0 ⎝

4 4 4 0 0

0 2 1 3 0

0 0 6 2 3

0⎞ 0 ⎟⎟ 0⎟ ⎟ 1⎟ 3 ⎟⎠

⎛ 8⎞ ⎜ ⎟ ⎜ −2 ⎟ ⎜ 14 ⎟ ⎜ ⎟ ⎜ 12 ⎟ ⎜ −3 ⎟ ⎝ ⎠

Решение:

⎧ai xi −1 − bi xi + ci xi +1 = di , i = 1,5 ⎨ ⎩a1 = c5 = 0. Система, согласно условиям будет иметь вид

− 2 x1 + 4 x2

= 8,

x1 − 4 x2 + 2 x3

= −2,

4 x2 − 1x3 + 6 x4

= 14,

3 x3 − 2 x4 + x5 = 12, 3 x4 − 3 x5 = −3. Используем рекуррентные соотношения (5), (6). Из первого уравнения следует

x1 = 2 x2 − 4, ξ 2 = 2, η2 = −4

Далее: 10

ξ3 =

c2 2 = = 1, b2 − a2ξ 2 4 − 1 ⋅ 2

ξ4 =

c3 6 = = −2, b3 − a3ξ3 1 − 4 ⋅ 1

η3 =

d 2 − a2η 2 −2 − 1 ⋅ (−4) = = −1, a2ξ 2 − b2 1⋅ 2 − 4

η4 =

d3 − a3η3 14 − 4 ⋅ (−1) = = 6, a3ξ3 − b3 4 ⋅1 − 1

ξ5 =

c4 1 = , b4 − a4ξ 4 8

ξ6 = 0, η6 =

d −a η 3 η5 = 4 4 4 = , a4ξ 4 − b4 4

d5 − a5η5 = 2. a5ξ5 − b5

Тогда:

x5 = η6 = 2, 1 3 x4 = ξ5 x5 + η5 = ⋅ 2 + = 1, 8 4 x3 = ξ 4 x4 + η4 = −2 ⋅ 1 + 6 = 4, x2 = ξ3 x3 + η3 = 1 ⋅ 4 − 1 = 3, x1 = ξ 2 x2 + η2 = 2 ⋅ 3 − 4 = 2. Ответ: x1 = 2,

x2 = 3, x3 = 4,

x4 = 1, x5 = 2 .

Упражнения Решить системы уравнений методом Гаусса: 1.

⎧2 x1 + 4 x2 + 3 x3 = 4, ⎪ ⎨3 x1 + x2 − 2 x3 = −2, ⎪4 x + 11x + 7 x = 7. 2 3 ⎩ 1 Ответ: ( 1; − 1; 2 ) . 2.

⎧ x1 + 2 x2 + 3 x3 = 6, ⎪ ⎨2 x1 + 3 x2 − x3 = 4, ⎪3 x + x − 4 x = 0. 3 ⎩ 1 2 Ответ:

( 1; 1; 1) .

3.

⎧2 x1 + x2 + 3 x3 − x4 = 10, ⎪ x + 2 x − 5 x + 2 x = 9, ⎪ 1 2 3 4 ⎨ ⎪− x1 − 7 x2 + 4 x3 + 5 x4 = 1, ⎪⎩−2 x1 + 4 x2 + x3 − x4 = − 2. Ответ: ( 4; 2;1; 3) . 4.

11

⎧2 x1 + 3 x2 − x3 + x4 = 5, ⎪3 x − x + 2 x + x = 1, ⎪ 1 2 3 4 ⎨ ⎪ x1 + 2 x2 + 3 x3 + 4 x4 = 6, ⎪⎩6 x1 + 4 x2 + 4 x3 + 6 x4 = 1. Ответ: Несовместна. 5.

⎧ x1 + 2 x2 − x3 = 7, ⎪ ⎨2 x1 − 3 x2 + x3 = 3, ⎪4 x + x − x = 16. 3 ⎩ 1 2 Ответ: Несовместна. 6.

⎧3 x1 − 2 x2 + 3 x3 − 3 x4 = 0, ⎪ ⎨3 x1 − 2 x2 − x3 + x4 = 0, ⎪ x − x + 2 x + 5 x = 0. 2 3 4 ⎩ 1 Ответ: (14c; 21c; c; c ) , где c –любое число. 7.

⎧2 x1 − x2 + x3 − x4 = 5, ⎪ ⎨ x1 + 2 x2 − 2 x3 + 3 x4 = −6, ⎪3 x + x − x + 2 x = −1. 2 3 4 ⎩ 1 ⎛ ⎝

Ответ: ⎜ x1 =

4 1 17 7 ⎞ − c2 ; x2 = − + c1 − c2 ; x3 = c1; x4 = c2 ⎟ , где c1 , c2 – 5 5 5 5 ⎠

любые числа. 8.

⎧2 x1 + x2 + x3 + x4 = 1, ⎪ x2 − x3 + 2 x4 = 2, ⎨ ⎪2 x + 2 x + 5 x4 = 3. 2 ⎩ 1 ⎛ ⎝

Ответ: ⎜ −c1 +

1 1 ⎞ c2 − ; c1 − 2c2 + 2; c1; c2 ⎟ , где c1; c2 – любые числа. 2 2 ⎠

9. Решить систему методом Гаусса с выбором главного элемента с точностью до четырех значащих цифр:

x + 592 y = 437,

592 x + 4308 y = 2251 10. Решить методом прогонки.

⎛ 5 10 0 0 ⎜3 2 7 0 ⎜ ⎜ 0 4 6 −3 ⎜ ⎜ 0 0 −5 4 ⎜ 0 0 0 12 ⎝

0⎞ 0 ⎟⎟ 0⎟ ⎟ 8⎟ 6 ⎟⎠

⎛ −5 ⎞ ⎜ 12 ⎟ ⎜ ⎟ ⎜ −10 ⎟ ⎜ ⎟ 11 ⎜ ⎟ ⎜ 6 ⎟ ⎝ ⎠ 12

Ответ: ( 2,

0.5, 1, 2, 3)

11. Методом прогонки решить систему

⎧2 x1 + x2 ⎪ ⎪⎪2 x1 + 9 x2 + 2 x3 4 x2 + 17 x3 − 4 x4 ⎨ ⎪ 4 x3 + 15 x4 − 8 x5 ⎪ ⎪⎩ 2 x4 + 3 x5 Ответ: ( −4, − 2, 0, 2, 4 )

= − 10, = − 26, = − 16, = − 2, = 16.

Методы, основанные на разложении матрицы коэффициентов. Такие методы основаны на представлении матрицы составленной из коэффициентов СЛАУ в форме произведения треугольных матриц. Это позволяет свести решение заданной системы к последовательному решению двух систем с треугольными матрицами, что является задачей более простой, так как в них неизвестные находятся последовательно. Иногда для придания вычислениям единообразия вводят еще диагональную матрицу. 1.5 Метод квадратного корня (случай эрмитовой матрицы) Итак, рассмотрим систему ЛАУ, где матрица A является эрмитовой

Ax = f .

(7)

Найдем такую правую треугольную матрицу S и диагональную матрицу D , элементы которой равны 1 или –1, чтобы A имела представление

A = S ∗ DS , ∗

где матрица S является cопряженной по отношению к матрице S .

⎛ s11 s12 ⎜ 0 s 22 S =⎜ ⎜K K ⎜⎜ 0 ⎝ 0

K s1n ⎞ K s2 n ⎟⎟ , K K⎟ ⎟ K snn ⎟⎠

⎛ d11 0 ⎜ 0 d 22 D=⎜ ⎜K K ⎜⎜ 0 ⎝ 0

0 ⎞ K 0 ⎟⎟ K K⎟ ⎟ K d nn ⎟⎠

K

Если матрицы S и D найдены, то заданная система (7) может быть решена следующим путем:

(

)

Ax = S * DS x = S *D S x = By = f , *

где S D = B есть нижняя треугольная матрица и y = Sx – вспомогательный вектор. Решение системы (7) равносильно решению двух треугольных систем

By = f

и Sx = y

Общие расчетные формулы. i −1 ⎛ ⎞ 2 dii = sign ⎜ aii − ∑ sli dll ⎟ l =1 ⎝ ⎠

(8) 13

i −1 ⎛ 2 sii = ⎜ aii − ∑ sli dll ⎜ l =1 ⎝

⎞ ⎟⎟ ⎠

1

2

(9)

i −1

sij =

aij − ∑ sli slj dll l =1

sii dii

,

при

i< j

(10)

По формулам (8)–(10) находятся рекуррентно все ненулевые элементы матриц D и S. Условием возможности нахождения sij является неравенство sii ≠ 0 . *

Замечание: Алгоритм S DS – разложения может оказаться численно неустойчивым, гарантировать устойчивость алгоритма можно в двух случаях – для положительно определенных матриц А и матриц с диагональным преобладанием. 1.6 Частный случай метода квадратного корня (случай симметричной матрицы) Рассматриваем область вещественных чисел. Пусть матрица A системы (7) – положительно определенная. Идея метода: Метод основан на разложении матрицы A на множители,

A = T TT ,

(11)

где

⎛ t11 t12 ⎜0 t 22 T =⎜ ⎜K K ⎜⎜ ⎝0 0

K t1m ⎞ K t2 m ⎟⎟ , K K ⎟ ⎟ K tm m ⎟⎠

⎛ t11 ⎜t 12 T T =⎜ ⎜K ⎜⎜ ⎝ t1m

K 0 ⎞ t22 K 0 ⎟⎟ K K K ⎟ ⎟ t2 m K tm m ⎟⎠ 0

Решение системы (7) сводится к решению двух систем с треугольными матрицами:

T T y = f , Tx = y

(12)

Прямой ход: T

Перемножая матрицы T и T , и приравнивая матрице A , из (11) получим следующие формулы для определения tij

14

t11 = a11 , t1 j =

a1 j

( j > 1),

t11

i −1

tii = aii − ∑ tk2 i

(1 < i ≤ m),

k =1

(13)

i −1

tij =

aij − ∑ tk itk j k =1

(i < j ),

tii

tij = 0 при i > j. После того, как матрица T найдена, решаем задачу (12). Обратный ход: Записываем в развернутом виде системы (12):

t11 y1 = f1, t12 y1 + t22 y2 = f 2 , ........................... t1m y1 + t2 m y2 + K + tmm ym = f m, t11x1 + t12 x2 + K + t1m xm = y1, t22 x2 + K + t2 m xm = y2 , ........................................... tmm xm = ym Отсюда последовательно находим i −1

f y1 = 1 , t11

xm =

ym t mm

,

yi =

xi =

fi − ∑ tki yk k =1

tii yi −

(i > 1)

(14)

m

∑ ti k xk

k =i +1

t ii

(i < m)

(15)

Пример 1. Методом квадратных корней решить системы уравнений. Вычисления вести с пятью знаками после запятой.

⎧ x1 + 0, 42 x2 + 0,54 x3 + 0, 66 x4 = 0,3 ⎪ ⎪0, 42 x1 + x2 + 0,32 x3 + 0, 44 x4 = 0,5 ⎨ ⎪0,54 x1 + 0,32 x2 + x3 + 0, 22 x4 = 0, 7 ⎪⎩0, 66 x1 + 0, 44 x2 + 0, 22 x3 + x4 = 0,9 Решение. Прямой ход. 15

Находим tij при n = 4 из формул (13):

t11 = a11 = 1 = 1; t12 =

a12 a a = 0, 42; t13 = 13 = 0,54; t14 = 14 = 0,66; a11 a11 a11

2 = 1 − 0,422 = 0,90752; t22 = a22 − t12

a23 − t12t13 0,32 − 0,42 ⋅ 0,54 = = 0,10270; t22 0,90752 a −t t 0,44 − 0,42 ⋅ 0,66 = 24 12 14 = = 0,17939; t22 0,90752

t23 = t24

2 2 t33 = a33 − t13 − t23 = 0,83537; a −t t −t t t34 = 34 13 14 23 24 = −0,18533; t33 2 2 2 t44 = a44 − t14 − t24 − t34 = 0,70560.

Обратный ход. Находим yi ( i = 1, 2,3,4 ) из формул (14)

y1 = y3 =

f1 0,3 = = 0,30; t11 1

y2 =

f 2 − t12 y1 0,5 − 0,42 ⋅ 0,3 = = 0, 41211; t22 0,90752

f3 − t13 y1 − t23 y2 0,7 − 0,54 ⋅ 0,3 − 0,10270 ⋅ 0,41211 = = 0,59336; t33 0,83537

f 4 − t14 y1 − t24 y2 − t34 y3 = 1,04597. t44 Находим xi ( i = 1,2,3,4 ) из формул (15) y −t x 1,04597 y = 1, 48238; x3 = 3 34 4 = 1,03917; x4 = 4 = t44 0,70560 t33 y4 =

x2 =

y2 − t23 x3 − t24 x4 y −t x −t x −t x = 0,04348; x1 = 1 12 2 13 3 14 4 = −1, 25778. t22 t11 Пример 2.

− 2 x5 = 0,5 ⎧ x1 + 3 x2 − 2 x3 ⎪ ⎪ 3 x1 + 4 x2 − 5 x3 + x4 − 3 x5 = 5, 4 ⎪ ⎨−2 x1 − 5 x2 + 3 x3 − 2 x4 + 2 x5 = 5, 0 ⎪ x2 − 2 x3 + 5 x4 + 3 x5 = 7,5 ⎪ ⎪− ⎩ 2 x1 − 3 x2 + 2 x3 + 3 x4 + 4 x5 = 3,3 Решение. Прямой ход. Находим tij при n = 5 из формул (13), при этом некоторые значения tij оказываются чисто мнимыми:

16

t11 = a11 = 1; t12 =

a12 = 3; t13 = −2; t14 = 0; t15 = −2; a11

2 t22 = a22 − t12 = 4 − 32 = i 5 = 2, 2361 i;

t23 =

a23 − t12t13 −5 − 3(−2) = = −0,4472 i; 2,2361 i t22

t24 =

a24 − t12t14 = −0,4472 i; t22

t25 =

a25 − t12t15 = −1,3416 i; t22

2 2 t33 = a33 − t13 − t23 = 0,8944 i;

t34 =

a34 − t13t14 − t23t24 = 2,0125 i; t33

2 2 2 t44 = a44 − t14 − t24 − t34 = 3,0414;

t35 =

a35 − t13t15 − t23t25 = 1,5653 i; t33

t45 = 2,2194;

t55 = 0,8221 i. Обратный ход. Находим yi

y1 =

( i = 1,5) из формул (14)

f1 = 0,5; t11

y2 =

f 2 − t12 y1 = −1,7471 i; t22

y3 =

f3 − t13 y1 − t23 y2 = −7,5803 i; t33

y4 =

f 4 − t14 y1 − t24 y2 − t34 y3 = −2,2928; t44

y5 = 0,1643 i. Находим xi

( i = 1,5) из формул (15)

x5 =

y5 y −t x = 0,1998; x4 = 4 45 5 = −0,8996; t55 t44

x3 =

y3 − t35 x5 − t34 x4 = −6,8011; t33

x2 = −2,2016; x1 = −6,0978. 1.7 Схема Холецкого (случай матрицы с отличными от 0 главными минорами). Рассматриваем систему уравнений (7), где матрица A размера n × n такая, что ее главные миноры отличны от нуля. Теорема 1. Если главные миноры матрицы A отличны от нуля, то матрицу A можно представить в форме

A = BC , где 17

0 ⎛ b11 0 ⎜b b 0 B = ⎜ 21 22 ⎜K K K ⎜⎜ ⎝ bn1 bn 2 bn3

0 ⎞ K 0 ⎟⎟ , K K⎟ ⎟ K bnn ⎟⎠

⎛ 1 c12 K c1n ⎞ ⎜0 1 K c ⎟ 2n ⎟ C =⎜ . ⎜K K K K ⎟ ⎜ ⎟ ⎝0 0 0 1 ⎠

K

Тогда элементы bij и cij будут определяться по формулам

bi1 = ai1, j −1

bij = aij − ∑ bik ckj

(i ≥ j > 1)

(16)

k =1

и

c1 j =

a1 j b11

,

i −1 ⎞ 1⎛ cij = ⎜ aij − ∑ bik ckj ⎟ (1 < i < j ) bii ⎝ k =1 ⎠

(17)

Отсюда искомый вектор x может быть вычислен из цепи уравнений

By = f ,

Cx = y

(18)

Так как матрицы B и C треугольные, то система (18) легко решается:

y1 = f1 b11, i −1 ⎛ ⎞ yi = ⎜ fi − ∑ bik yk ⎟ bii k =1 ⎝ ⎠

(i > 1)

(19)

xn = yn , xi = yi −

n

∑ cik xk

(i < n).

(20)

k =i +1

Из формулы (19) видно, что числа

yi выгодно вычислять вместе с

коэффициентами cij . Эта схема вычислений называется схемой Холецкого.

Упражнения Методом квадратных корней решить системы уравнений Ax = f . Вычисления вести с пятью знаками после запятой.

⎛ 3,1 1,5 1,0 ⎞ A = ⎜⎜ 1,5 2,5 0,5 ⎟⎟ , ⎜1,0 0,5 4,2 ⎟ ⎝ ⎠

⎛10,83 ⎞ f = ⎜⎜ 9, 20 ⎟⎟ . 1. ⎜ 17,10 ⎟ ⎝ ⎠ Ответ: указаны точные значения x1 = 1,3; x2 = 2,2; x3 = 3,5.

18

1 ⎞ ⎛ 3, 2 1 ⎛ 4 ⎞ ⎜ ⎟ ⎜ 4,5 ⎟ . 3,7 1 , f = 2. A = 1 ⎜ ⎟ ⎜ ⎟ ⎜ 1 ⎟ ⎜ 5 ⎟ 1 4, 2 ⎝ ⎠ ⎝ ⎠ Ответ: x1 = 0,74481; x2 = 0,79206; x3 = 0,82455. ⎛ 2,12 ⎜ 0,42 A=⎜ ⎜ 1,34 ⎜ ⎝ 0,88

0,88 ⎞ ⎛ 11,172 ⎞ ⎟ ⎜ 0,115 ⎟ 3,95 1,87 0,43 ⎟ ⎟. 3. , f =⎜ ⎜ 9,009 ⎟ 1,87 2,98 0,46 ⎟ ⎟ ⎜ ⎟ 0,43 0, 46 4,44 ⎠ ⎝ 9,349 ⎠ Ответ: указаны точные значения x1 = 3,7; x2 = −1,5; x3 = 2,1; x4 = 1,3. 0,42 1,34

6 5,5 ⎞ ⎛ 5,5 7 ⎛ 23 ⎞ ⎜ 7 10,5 8 ⎜ 32 ⎟ 7 ⎟⎟ ⎜ 4. A = , f = ⎜ ⎟. ⎜ 6 ⎜ 33 ⎟ 8 10,5 9 ⎟ ⎜ ⎟ ⎜ ⎟ 9 10,5 ⎠ ⎝ 5,5 7 ⎝ 31 ⎠ Ответ: x1 = 0,2927; x2 = 1,4196; x3 = 1,1799; x4 = 0,89104. ⎛ 16 ⎜ −8 5. A = ⎜ ⎜ −4 ⎜ ⎝ 0

−8 −4

0⎞ 13 −4 −3 ⎟⎟ , −4 9 0 ⎟ ⎟ −3 0 3 ⎠

⎛ −8 ⎞ ⎜7⎟ f = ⎜ ⎟. ⎜6⎟ ⎜ ⎟ ⎝ −3 ⎠

Решить системы уравнений Ax = f , пользуясь схемой Холецкого.

−3 4,6 ⎞ ⎛ 2,5 ⎛ −1,05 ⎞ ⎜ ⎟ ⎜ −14,46 ⎟ . f = 1. A = −3,5 2,6 1,5 , ⎜ ⎟ ⎜ ⎟ ⎜ −6,5 −3,5 7,3 ⎟ ⎜ −17,735 ⎟ ⎝ ⎠ ⎝ ⎠ Ответ: x1 = 1,24; x2 = −2,45; x3 = −2,5. ⎛ 2 −4 −3, 25 1 ⎞ ⎛ 4,84 ⎞ ⎜ 3 −3 −4,3 ⎟ ⎜ 8,89 ⎟ 8 ⎟, ⎟. 2. A = ⎜ f =⎜ ⎜ 1 −5 3,3 −20 ⎟ ⎜ −14,01 ⎟ ⎜ ⎟ ⎜ ⎟ 2 −3 ⎠ ⎝ 2,5 −4 ⎝ −20, 29 ⎠ Ответ: x1 = 2,34; x2 = 4,51; x3 = −6; x4 = −1,3.

19

⎛ 2 −1 4 ⎜ −1 1 2 ⎜ 3. A = ⎜ 4 2 3 ⎜ ⎜ −3 1 3 ⎜ 1 3 −1 ⎝ Ответ: x1 = 1; x2 = 2;

−3

1⎞ ⎛ 11 ⎞ ⎟ ⎜14 ⎟ 1 3⎟ ⎜ ⎟ f =⎜ 4 ⎟. 3 −1 ⎟ , ⎟ ⎜ ⎟ 2 4⎟ ⎜ 16 ⎟ ⎜ 18 ⎟ 4 4 ⎟⎠ ⎝ ⎠ x3 = 1; x4 = −1; x5 = 4.

2. Приближенные методы. Метод называется приближенным, если при точном выполнении всех требуемых действий и при точных коэффициентах мы получаем, как правило, лишь приближенный результат. Впрочем, практически и при применении точного метода результат оказывается также приближенным по двум причинам: во-первых, коэффициенты уравнений обычно бывают приближенными числами; во-вторых, промежуточные вычисления на практике обычно невозможно выполнять с полной точностью. Значит, погрешность окончательного результата складывается из неустранимой погрешности задания исходных данных (коэффициентов) и погрешностей округления. В случае применения приближенного метода на окончательный результат влияет всегда погрешность метода, также на практике обычно имеет место неустранимая погрешность в задании коэффициентов и погрешность округления в промежуточных действиях. В данном разделе рассматриваются следующие приближенные методы: метод простой итерации, метод Зейделя, метод релаксаций. Итерационные методы дают возможность найти решение системы, как предел последовательных приближений, по предыдущим (уже найденным) приближениям к решению строятся следующие более точные приближения. Если в точных методах ошибка в вычислениях ведет к ошибке в результате, то в случае сходящегося итерационного процесса ошибка в каком-то приближении исправляется в последующих вычислениях, и такое исправление требует, как правило, только несколько лишних шагов единообразных вычислений. Итерационный метод, для того чтобы начать по нему вычисления, требует знания одного или нескольких начальных приближений к решению. Условия и скорость сходимости каждого итерационного процесса существенно зависят от свойств уравнений, то есть от свойств матрицы системы, и от выбора начальных приближений. 2.1 Метод простой итерации. Одношаговый линейный стационарный итерационный процесс называется методом простой итерации (МПИ). Пусть дана система ЛАУ Ax = f с неособенной матрицей. В методе простой итерации ее предварительно приводят к виду

x = Bx + c , Предположим, что известно приближение x решению правилом

x* = ( x1* ,K, xn* )

(1) (0)

= ( x1(0) ,K, xn(0) ) к точному

системы. Все следующие приближения определим

20

x ( k +1) = Bx ( k ) + c, k = 0,1, 2,K Если

последовательность

x(k )

приближений

(2)

сходится

к

некоторому

*

предельному вектору x , то он и будет решением системы. Действительно, если в равенстве (2) перейти к пределу k → ∞ , считая, что x

(k )

→ x* , то в пределе получим

x* = Bx* + c . Условия сходимости последовательности x

(k )

: (k )

Теорема 1. Для того чтобы последовательность приближений x сходилась, достаточно, чтобы все собственные значения матрицы В были по модулю меньше 1:

λi < 1 (i = 1,2,K, n)

(3)

Доказательство: Найдем выражение любого приближения x

(k )

0

через x :

x ( k ) = Bx ( k −1) + c = B ⎡⎣ Bx ( k −2) + c ⎤⎦ + c = B 2 x ( k −2) + ( E + B ) c = k (0)

K= B x

(

+ E + B +K+ B

k −1

(*)

)c

Отсюда и из (3) следует с учетом теоремы о сходимости ряда матричной k

геометрической прогрессии 1 сразу следует, что при k → ∞ B → 0 и −1

E + B + K + B k −1 → E + B + B 2 + K = ( E − B ) , откуда x

(k )

−1

→ ( E − B ) c = x*

#

Что касается необходимости условия (3), то ответ на такой вопрос дает Теорема 2. Если требовать, чтобы последовательность x

при любом начальном приближении x Доказательство:

(0)

) (

сходилась к x

(0)

будет x

) (

(k )

→ x* . Имеем

)

(

x* − x ( k ) = Bx* + c − Bx ( k −1) + c = B x* − x ( k −1) = K = B k x* − x (0) *

При k → ∞ разность x − x

*

, то условие (3) является и необходимым.

Пусть для всякого начального приближения x

(

(k )

)

(k )

→ 0 , поэтому последний член цепи равенства * (0) должен стремиться к нулю, каким бы ни был вектор x − x . Отсюда следует, что B k → 0 , последнее же будет лишь в том случае, когда верно неравенство (3) (см. # лемму2). 2

m

Теорема: Для того чтобы ряд E + A + A + K + A + K (матричная геометрическая прогрессия) сходился, необходимо и достаточно, чтобы все собственные значения матрицы А были по модулю меньше единицы. При выполнении этого условия матрица Е-А имеет обратную и верно равенство 1

E = A + A 2 + K + Am + K = ( E − A )

−1

m

Лемма Для стремления A к нулю при m → ∞ , необходимо и достаточно, чтобы все собственные значения матрицы А по модулю были меньше единицы. 2

21

Применение теорем 1 и 2 требует знания границ собственных значений матрицы B , нахождение их часто затруднено. Укажем более простые, но только достаточные признаки сходимости. (k )

Теорема 3. Для того чтобы последовательность приближений x в методе простой итерации сходилась, достаточно, чтобы какая-либо норма матрицы B была меньше единицы. Доказательство: При доказательстве используем лемму: Модули собственных значений матрицы не превосходят любой из ее норм. Если B < 1 , то по лемме все собственные значения матрицы B по модулю (k )

меньше единицы, и по теореме 1 последовательность x сходится. Непосредственным следствием теоремы 3 и равенств n

B I = max ∑ bij ; i

B

j =1

#

n

II

= max ∑ bij , j

i =1

определяющих кубическую и октаэдрическую норму матрицы, является (k )

в м-де простой итерации сходится , если Теорема 4. Последовательность x для матрицы В выполняется одно из неравенств: n

1)

∑ bij

≤α <1

(i = 1,2,K, n),

(4)

≤ β <1

( j = 1,2,K, n).

(5)

j =1 n

2)

∑ bij i =1

Для многих приложений важно знать, какой является скорость сходимости

→ x* , и уметь оценить погрешность x* − x ( k ) замены точного решения x* (k ) системы приближением x . (k ) Оценка погрешности приближенного решения x дается одной из следующих x

(k )

формул:

xi − xi ( k ) ≤

α max x j ( k ) − x j ( k −1) , 1 − α j =1,2,K,n

(4`)

если выполнено (4). И

xi − xi

(k )

≤

β

n

x j ( k ) − x j ( k −1) , ∑ 1− β

(5`)

j =1

если выполнено (5). Эти оценки можно еще усилить соответственно так:

max xi − xi ( k ) ≤ n

или

∑ xi − xi i =1

(k )

≤

α max xi ( k ) − xi ( k −1) 1−α β

(4``)

n

xi ( k ) − xi ( k −1) ∑ 1− β

(5``)

i =1

Процесс итерации заканчивают, когда указанные оценки свидетельствуют о достижении заданной точности.

22

Теорема 5. Если какая-либо норма матрицы B , согласованная с рассматриваемой нормой вектора x , меньше единицы, то верна следующая оценка погрешности приближения в методе простой итерации:

x* − x ( k ) ≤ B

k

x (0) +

1 B 1− B

k

c

(6)

Док-во: Для x

(k )

в доказательстве теоремы (1) выше дано выражение (*), и так как

(

) = (B

B < 1 , то x* = E + B + B 2 + K c . Поэтому x* − x ( k ) и, стало быть,

(

x* − x ( k ) ≤ B

k

Часто за x упростится:

+ B (0)

k +1

k

)

+ B k +1 + K c − B k x (0)

)

+K c + B

k

x (0) = B

k

x (0) +

1 B 1− B

k

c .#

принимают вектор c . В этом случае оценка (6) немного

x* − x ( k ) ≤

1 B 1− B

k +1

c .

МПИ в координатной форме имеет вид:

⎧ x1( k +1) = b11 x1( k ) + b12 x2( k ) + K + b1n xn ( k ) + c1 ⎪ ( k +1) = b21 x1( k ) + b22 x2( k ) + K + b2 n xn ( k ) + c2 ⎪ x2 ⎨ ⎪.................................................................... ⎪ ( k +1) = bn1 x1( k ) + b22 x2( k ) + KK + bnn xn ( k ) + cn ⎩ xn

(7)

Покажем на примерах два способа приведения исходной системы к виду (1) Пример 1.

Решить систему методом простой итерации

⎧20 x1 + x2 + 2 x3 + 0,5 x4 = 14,1 ⎪2 x + 10 x + x + 2 x = 15 ⎪ 1 2 3 4 ⎨ ⎪ x1 + 3 x2 + 15 x3 + 3 x4 = 25,7 ⎪⎩4 x1 + 2 x2 + x3 + 24 x4 = 38,8 Решение: В исходной системе уравнений диагональные коэффициенты заметно превосходят остальные. Чтобы привести систему к виду (1), поделим уравнения на диагональные коэффициенты и решим каждое из уравнений относительно полученных на диагонали неизвестных с коэффициентом 1 .

23

1 (14,1 − x2 − 2 x3 − 0,5 x4 ) 20 1 x2 = (15 − 2 x1 − x3 − 2 x4 ) 10 1 x3 = ( 25,7 − x1 − 3 x2 − 3 x4 ) 15 1 x4 = ( 38,8 − 4 x1 − 2 x2 − x3 ) 24 1 1 ⎛ − − ⎜ 0 20 10 ⎜ 1 ⎜ −1 0 − ⎜ 5 10 Здесь B = ⎜ ⎜− 1 −1 0 5 ⎜ 15 ⎜ 1 1 1 − − ⎜− 12 24 ⎝ 6 x1 =

1 ⎞ ⎛ 14,1 ⎞ 40 ⎟ ⎜ 20 ⎟ ⎟ ⎜ ⎟ 1 1,5 ⎟ − ⎟ ⎜ 5 ⎟ ⎟ , c = ⎜ 25,7 ⎟ . 1 ⎟ ⎜ ⎟ − 15 ⎟ ⎜ 5 ⎟ ⎜ 38,8 ⎟ ⎟ ⎜ ⎟ 0 ⎟ ⎝ 24 ⎠ ⎠

−

Заметим, что коэффициенты полученной системы удовлетворяют условию B < 1. В качестве нормы матрицы В рассмотрим первую кубическую норму n

B I = max ∑ Bij i

j =1

4

4

4

j =1

j =1

j =1

∑ B1 j =0,175<1, ∑ B2 j =0,5<1, ∑ B3 j

≈ 0,466<1,

4

∑ B4 j

≈ 0,125<1

j =1

α = 0,5. Так что α точность k-го приближения может быть оценена по формуле (4``) при = 1. 1−α Таким образом, сходимость итераций гарантирована. При этом

(0)

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

x (0)

⎛ 0,72 ⎞ ⎜ 1,50 ⎟ ⎟ =⎜ ⎜ 1,71 ⎟ ⎜ ⎟ ⎝ 1,62 ⎠ (k )

Вычисления будем вести до тех пор, пока величины xi

− xi( k −1) (i=1,2,3,4) не

−2

станут меньше ε = 10 (обычно ε берется меньше, но мы задачу упростили). Последовательно вычисляем при k = 1

24

1 (14,1 − 1,5 − 3, 42 − 0,81) ≈ 0,42 20 1 x2(1) = (15 − 1, 44 − 1,71 − 3, 24 ) ≈ 0,86 10 1 x3(1) = ( 25,7 − 0,72 − 4,5 − 4,86 ) ≈ 1,04 15 1 x4(1) = ( 38,8 − 2,88 − 3 − 1,71) ≈ 1,30 24 x1(1) =

при k = 2

1 20 1 x2(2) = 10 1 x3(2) = 15 1 x4(2) = 24 x1(2) =

(14,1 − x

2

)

(1)

(15 − 2 x

(1) 1

( 25,7 − x

− 2 x3(1) − 0,5 x4(1) =

(1) 1

(38,8 − 4 x

)

− x3(1) − 2 x4(1) = − 3 x2(1) − 3 x4(1)

(1) 1

)

− 2 x2(1) − x3(1)

1 (14,1 − 0,86 − 2,08 − 0,65) ≈ 0,53 20

1 (15 − 0,84 − 1,04 − 2,6 ) ≈ 1,05 10 1 = ( 25,7 − 0,42 − 2,58 − 3,9 ) ≈ 1,25 15 1 = ( 38,8 − 1,68 − 1,72 − 1,04 ) ≈ 1,43 24

)

при k = 3

x1(3) ≈ 0,50,

x2(3) ≈ 1,00,

x3(3) ≈ 1, 21,

x4(3) ≈ 1,40

при k = 4

x1(4) ≈ 0,50,

x2(4) ≈ 1,00,

x3(4) ≈ 1,20,

x4(4) ≈ 1,40

при k = 5

x1(5) ≈ 0,50,

x2(5) ≈ 1,00,

x3(5) ≈ 1,20,

x4(5) ≈ 1, 40

(k )

Вычисляем модули разности значений xi

− xi( k −1) между четвертым и пятым

приближениями. Все они меньше 0,01= ε , поэтому их можно взять в качестве решения. Пример 2 Решить систему методом простой итерации, произведя три итерации. Указать погрешность полученного результата.

⎧1,02 x1 − 0,05 x2 − 0,10 x3 = 0,795 ⎪ ⎨−0,11x1 + 1,03 x2 − 0,05 x3 = 0,849 ⎪−0,11x − 0,12 x + 1,04 x = 1,398 1 2 3 ⎩ Решение: Матрица данной системы такова, что диагональные элементы близки к единице, а все остальные значительно меньше единицы. Вычленим единицу из каждого диагонального коэффициента и выразим полученные таким образом x1 , x2 , x3 из 1, 2 и 3-го уравнений соответственно:

⎧ x1 = 0,795 − 0,02 x1 + 0,05 x2 + 0,10 x3 ⎪ ⎨ x2 = 0,849 + 0,11x1 − 0,03 x2 + 0,05 x3 ⎪ x = 1,398 + 0,11x + 0,12 x − 0,04 x 1 2 3 ⎩ 3 25

0,1 ⎞ ⎛ −0,02 0,05 ⎛ 0,795 ⎞ ⎜ ⎟ ⎜ ⎟ В этой системе B = 0,11 −0,03 0,05 , c = 0,849 . ⎜ ⎟ ⎜ ⎟ ⎜ 0,11 ⎟ ⎜ 1,398 ⎟ 0,12 0,04 − ⎝ ⎠ ⎝ ⎠ Условия сходимости для полученной системы выполнены 3

3

3

j =1

j =1

j =1

∑ B1 j =0,17<1, ∑ B2 j =0,19<1, ∑ B3 j =0,27<1 Таким образом, сходимость итераций гарантирована. При этом α = 0,27. Так что точность k-го приближения может быть оценена по формуле (4``) при

0,27 ≈ 0,3699 . 1 − 0,27 (0)

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

x (0)

⎛ 0,80 ⎞ = ⎜⎜ 0,85 ⎟⎟ ⎜ 1, 40 ⎟ ⎝ ⎠

Далее последовательно находим при k = 1

x1(1) = 0,795 − 0,016 + 0,0425 + 0,140 = 0,9615 ≈ 0,962 x2(1) = 0,849 + 0,088 − 0,0255 + 0,070 = 0,9815 ≈ 0,982 x3(1) = 1,398 + 0,088 + 0,1020 − 0,056 = 1,532 при k = 2 x1(2) = 0,97806 ≈ 0,978, x2(2) = 1,00196 ≈ 1,002, x3(2) = 1,56038 ≈ 1,560 при k = 3

x1(3) = 0,980,

x2(3) = 1,004,

x3(3) = 1,563 −3

Значения неизвестных при k = 2 и k = 3 отличаются не более чем на 3 ⋅ 10 , поэтому если в качестве приближенных значений неизвестных взять x1 ≈ 0,980, x2 ≈ 1,004, x3 ≈ 1,563 , то погрешность этих приближений не превзойдет

0,27 ⋅ 3 ⋅ 10−3 < 1,1 ⋅ 10−3 . 1 − 0,27

Замечание. Если вид матрицы коэффициентов исходной системы не соответствует матрицам в рассмотренных примерах, то можно попробовать так переставить или преобразовать исходные уравнения, чтобы получить относительно большие диагональные коэффициенты. Упражнения. Решить системы Ax = f методом простой итерации. Продолжать итерации до (k )

тех пор, пока xi

− xi( k −1) не станет меньше указанного ε . Сравнить ответ с

данными точными значениями неизвестных. 1.

26

⎛ 1,02 −0,25 −0,30 ⎞ A = ⎜⎜ −0,41 1,13 −0,15 ⎟⎟ , ⎜ −0,25 −0,14 1,21 ⎟ ⎝ ⎠

⎛ 0,515 ⎞ f = ⎜⎜ 1,555 ⎟⎟ , ⎜ 2,780 ⎟ ⎝ ⎠

⎛ 2,0 ⎞ x = ⎜⎜ 2,5 ⎟⎟ , ⎜ 3,0 ⎟ ⎝ ⎠

ε = 10−3

2.

⎛10,9 1,2 2,1 0,9 ⎞ ⎜ 1,2 11,2 1,5 2,5 ⎟ ⎟, A=⎜ ⎜ 2,1 1,5 9,8 1,3 ⎟ ⎜ ⎟ ⎝ 0,9 2,5 1,3 12,1⎠

⎛ −7,0 ⎞ ⎜ 5,3 ⎟ ⎟, f =⎜ ⎜ 10,3 ⎟ ⎜ ⎟ ⎝ 24,6 ⎠

⎛ −1 ⎞ ⎜0⎟ x = ⎜ ⎟, ⎜1⎟ ⎜ ⎟ ⎝2⎠

ε = 10−3

3. Решить систему методом простой итерации, произведя три итерации. Указать погрешность полученного результата.

⎧5 x1 − x2 + x3 = 4, ⎪ ⎨0,5 x1 + 2 x2 − x3 = 1, ⎪ x − x + 4 x = 2. 2 3 ⎩ 1

2.2 Метод Зейделя. Метод Зейделя (МЗ) является модификацией метода простой итерации, его применяют в двух видоизменениях. Рассмотрим сначала случай канонической формы системы для метода итерации: x = Bx + b . 1. МЗ заключается в том, что при вычислениях (k+1)-го приближения неизвестного xi при i > 1 используются уже вычисленные ранее (k+1)-е приближения неизвестных x1 , x2 ,… xi −1 . Таким образом, для системы (1) расчеты ведутся по формулам

⎧ x1( k +1) = b11 x1( k ) + b12 x2( k ) + K + b1n xn ( k ) + c1 ⎪ ( k +1) = b21 x1( k +1) + b22 x2( k ) + K + b2 n xn ( k ) + c2 ⎪ x2 (8) ⎨ .................................................................... ⎪ ⎪ x ( k +1) = b x ( k +1) + b x ( k +1) + KK + b ( k +1) + bnn xn ( k ) + cn n1 1 n ,n−1 xn−1 22 2 ⎩ n То есть на k+1 шаге пускаем в расчет вычисленные k+1-е компоненты, остальные компоненты берем из предыдущего шага. i −1

n

j =1

j =i

xi ( k +1) = ∑ bi j x (jk +1) + ∑ bi j x j ( k ) + ci Разложим матрицу В на сумму двух матриц M и N, где

27

0 ⎛ 0 ⎜b ⎜ 21 0 M = ⎜ b31 b32 ⎜ ⎜K K ⎜ bn1 bn 2 ⎝

K K

0 0

K

0

K

K

K bn n−1

0⎞ 0 ⎟⎟ 0 ⎟, ⎟ K⎟ 0 ⎟⎠

⎛ b11 b12 ⎜ ⎜ 0 b22 N =⎜ 0 0 ⎜ ⎜K K ⎜⎜ 0 ⎝ 0

K b1 n−1 K b2 n−1 K b3 n−1 K

K

K

0

b1 n ⎞ ⎟ b2 n ⎟ b3 n ⎟ ⎟ K⎟ ⎟ bnn ⎟⎠

Тогда равенства для метода простой итерации (7) можно записать в форме матричного равенства

x ( k +1) = Mx ( k +1) + Nx ( k ) + c , ( k +1) откуда следует, что ( E − M ) x = Nx ( k ) + c , а так как определитель матрицы 0 ⎛ 1 ⎜ −b 1 E − M = ⎜ 21 ⎜ K K ⎜⎜ ⎝ −bn1 −bn 2

0⎞ K 0 ⎟⎟ K K⎟ ⎟ K 1 ⎟⎠ K

равен единице и она имеет обратную, то равенство (8) равносильно −1

−1

x ( k +1) = ( E − M ) Nx ( k ) + ( E − M ) c

(9)

Поэтому стационарный метод Зейделя равносилен методу простой итерации, примененному к системе −1

−1

x = ( E − M ) Nx + ( E − M ) c Условия сходимости для МПИ остаются верными и для метода Зейделя. Обычно МЗ дает лучшую сходимость чем МПИ (хотя это бывает не всегда). Кроме того МЗ может оказаться более удобным при программировании, так как при вычислениях

xi ( k +1) нет необходимости хранить значения x1( k ) , … , xi(−k1) .

2. Другая запись метода Зейделя. В ней требуется предварительное преобразование системы Ax = f к виду в котором все диагональные элементы отличны от нуля и если возможно даже доминирующими в соответствующих уравнениях (т.е. aii ≠ 0 и по возможности aii имели наибольшее значение в соответствующей строке, делается это путем перестановки столбцов в матрице А). Приближение k+1 находят по приближению k с помощью системы соотношений

a11x1( k +1) + a12 x2( k ) + a13 x3( k ) + K + a1n xn( k ) = f1, a21x1( k +1) + a22 x2( k +1) + a23 x3( k ) + K + a2 n xn( k ) = f 2 ,

........................................................................

(10)

an1x1( k +1) + an 2 x2( k +1) + an3 x3( k +1) + K + ann xn( k +1) = f n . Если разложить матрицу А на сумму двух матриц

⎛ a11 0 ⎜a a B = ⎜ 21 22 ⎜K K ⎜⎜ ⎝ an1 an 2

0 ⎞ K 0 ⎟⎟ , K K⎟ ⎟ K ann ⎟⎠ K

⎛ 0 a12 ⎜0 0 C =⎜ ⎜K K ⎜ ⎝0 0

K a1n ⎞ K a2 n ⎟⎟ , K K⎟ ⎟ K 0 ⎠ 28

то равенства (10) можно записать в матричном виде

Bx ( k +1) + Cx ( k ) = f

или

x ( k +1) = − B −1Cx ( k ) + B −1 f

Отсюда видно, что МЗ в форме (10) равносилен МПИ, примененному к системе −1

−1

в каноническом виде x = − B Cx + B f Для сходимости метода при любом векторе f необходимо и достаточно, чтобы все собственные значения матрицы

− B −1C , то есть все корни уравнения

− B −1C − λ E = 0 были по модулю меньше единицы. Пример. Для системы

⎧6 x1 − x2 − x3 = 11,33 ⎪ ⎨− x1 + 6 x2 − x3 = 32 ⎪− x − x + 6 x = 42 3 ⎩ 1 2 известны приближенные значения неизвестных, полученные методом Гаусса: x1 ≈ 4,67, x2 ≈ 7,62, x3 ≈ 9,05 . Методом Зейделя уточнить решения так, чтобы значения неизвестных

xi( k ) и xi( k +1) отличались не более чем на 5 ⋅ 10−3 . Решение. Приведем систему к виду

1 ⎧ x = (11,33 + x2 + x3 ) 1 ⎪ 6 ⎪ 1 ⎪ ⎨ x2 = ( 32 + x1 + x3 ) 6 ⎪ 1 ⎪ x = ( 42 + x1 + x2 ) 3 ⎪ 6 ⎩ Условия сходимости для полученной системы выполнены 3

∑ B1 j j =1

1 = <1, 3

3

∑ B2 j j =1

1 = <1, 3

3

∑ B3 j j =1

1 = <1 3

Таким образом, сходимость итераций гарантирована. При этом точность k-го приближения может быть оценена по формуле (4``) при Взяв в качестве начального приближения

1 3

α = . Так что 13 1 = . 1−1 3 2

x1(0) = 4,67 , x2(0) = 7,62 ,

x3(0) = 9,05 , получим 1 x1(1) = (11,33 + 16,67 ) = 4,66667 6 1 x2(1) = ( 32 + 13,71667 ) = 7,61944 6 1 x3(1) = ( 42 + 12,28611) = 9,04768 6 29

1 (11,33 + 16,66712 ) = 4,66619 6 1 x2(2) = ( 32 + 13,71387 ) = 7,61897 6 1 x3(2) = ( 42 + 12,28516 ) = 9,04752 6 x1(2) =

Т.к. для приведенной системы выполняется условие (4) при полученное приближение с оценкой (4``)

1 3

α = , то

имеет погрешность не превышающую

1 ⋅ 5 ⋅ 10−4 = 2,5 ⋅ 10−4 . Таким образом, в качестве решения можем принять 2 x1 ≈ 4,666, x2 ≈ 7,619, x3 ≈ 9,048 Упражнения. Решить системы методом Зейделя. Продолжать итерации до тех пор, пока

xi( k ) − xi( k −1) не станет меньше указанного ε . 1.

⎧20 x1 + x2 + 2 x3 + 0,5 x4 = 14,1 ⎪2 x + 10 x + x + 2 x = 15 ⎪ 1 2 3 4 ⎨ ⎪ x1 + 3 x2 + 15 x3 + 3 x4 = 25,7 ⎪⎩4 x1 + 2 x2 + x3 + 24 x4 = 38,8

ε = 10−2 .

2.

⎛ 1,02 −0,25 −0,30 ⎞ A = ⎜⎜ −0,41 1,13 −0,15 ⎟⎟ , ⎜ −0,25 −0,14 1,21 ⎟ ⎝ ⎠

⎛ 0,515 ⎞ f = ⎜⎜ 1,555 ⎟⎟ , ⎜ 2,780 ⎟ ⎝ ⎠

⎛ 2,0 ⎞ x = ⎜⎜ 2,5 ⎟⎟ , ⎜ 3,0 ⎟ ⎝ ⎠

ε = 10−3

3.

⎛10,9 1,2 2,1 0,9 ⎞ ⎜ 1,2 11,2 1,5 2,5 ⎟ ⎟, A=⎜ ⎜ 2,1 1,5 9,8 1,3 ⎟ ⎜ ⎟ ⎝ 0,9 2,5 1,3 12,1⎠

⎛ −7,0 ⎞ ⎜ 5,3 ⎟ ⎟, f =⎜ ⎜ 10,3 ⎟ ⎜ ⎟ ⎝ 24,6 ⎠

⎛ −1 ⎞ ⎜0⎟ x = ⎜ ⎟, ⎜1⎟ ⎜ ⎟ ⎝2⎠

ε = 10−3

4. Решить систему методом Зейделя, произведя три итерации. Указать погрешность полученного результата.

⎧1,1x1 − 0,2 x2 + 0,1x3 = 1,6 , ⎪ ⎨0,1x1 − 1,2 x2 − 0, 2 x3 = 2,3 , ⎪0, 2 x − 0,1x + 1,1x = 1,5 . 1 2 3 ⎩ 5. Решить систему методом Зейделя, произведя три итерации. Указать погрешность полученного результата, сравнить с решением МПИ, полученными ранее.

30

⎧1,02 x1 − 0,05 x2 − 0,10 x3 = 0,795 , ⎪ ⎨−0,11x1 + 1,03x2 − 0,05 x3 = 0,849 , ⎪−0,11x − 0,12 x + 1,04 x = 1,398 . 1 2 3 ⎩

Любой двухслойный канонической форме:

B

x ( k +1) − x ( k )

τ

( k +1)

Метод релаксации. итерационный метод можно записать в следующей

+ Ax ( k ) = f , k = 0,1,K, для всех x (0) ∈ H ,

(11)

где A : H → H – оператор исходного уравнения Ax = f , B : H → H линейный оператор, имеющий обратный B

−1

, k – номер итерации,τ

( k +1)

(1)

, τ (2) ,K,τ ( k +1) ,K –

итерационные параметры, τ > 0. Чтобы ускорить итерационный процесс, запишем метод Зейделя в виде итерационной схемы (11), введя параметр ω , так что

(D +ωA ) −

(

x ( k +1) − x ( k )

ω

)

где D = aiiδ ij ,

+ Ax ( k ) = f , k = 0,1,K, для всех x (0) ∈ H ,

(12)

δ ii = 1, δ ij = 0 при i ≠ j , т.е. D – диагональная матрица −

( ) −

размера n × n . A = ai j – нижняя треугольная (поддиагональная) матрица с нулями −

на главной диагонали, ai j = 0 при j ≥ i,

( )

ai−j = ai j при j < i . Введем обозначение

A+ = ai+j – верхняя треугольная (наддиагональная) матрица с нулями на главной ai+j = 0 при j ≤ i, ai+j = ai j при j > i .

диагонали,

Таким −

образом, +

рассматривается аддитивное представление исходной матрицы A = A + D + A . Сравнивая (12) с (11), видим, что

B = D + ω A− , τ = ω Покажем, что при ω = 1 получим формулу метода Зейделя. Преобразуем уравнение (12) к расчетному виду. Учитывая, что

(D +ωA ) −

x ( k +1) − x ( k )

ω

1 ⎞ 1 ⎞ ⎛ ⎛ + Ax ( k ) = ⎜ A− + D ⎟ x ( k +1) + ⎜ A − A− − D ⎟ x ( k ) = ω ⎠ ω ⎠ ⎝ ⎝

1 ⎞ 1⎞ ⎞ ⎛ ⎛ ⎛ = ⎜ A− + D ⎟ x ( k +1) + ⎜ A+ + ⎜ 1 − ⎟ D ⎟ x ( k ) , ω ⎠ ⎝ ⎝ ω⎠ ⎠ ⎝ имеем

1⎞ ⎞ ⎛ − 1 ⎞ ( k +1) ⎛ + ⎛ + ⎜ A + ⎜1 − ⎟ D ⎟ x( k ) = f . ⎜ A + D⎟x ω ⎠ ⎝ ⎝ ω⎠ ⎠ ⎝ 31

Отсюда находим

xi

( k +1)

= xi

(k )

+

ω⎡

i −1

⎢ fi − ∑ aii ⎣⎢ j =1

aij x (jk +1)

⎤ − ∑ aij x j ( k ) ⎥ , i = 1,2,..., n , j =i ⎦⎥ n

(13)

т.е. при ω = 1 получили формулу Зейделя. Скорость сходимости метода релаксации зависит от параметра ω . Для сходимости метода надо потребовать, чтобы 0< ω <2. При 0< ω <1 итерационный процесс (12) называют методом нижней релаксации, а при 1< ω <2 – методом верхней релаксации. Метод релаксации (и метод Зейделя) является примерами неявных схем вида

B

x ( k +1) − x ( k )

τ

+ Ax ( k ) = f , k = 0,1,K, для всех x (0) ∈ H −1

с несамосопряженным оператором B , имеющим обратный оператор B . Метод (12) называется стационарным итерационным методом, т.к. B и −1

τ не

зависят от номера итерации. Для существования обратного оператора B достаточно потребовать положительности оператора B . Теорема (Островского-Рейча) Для нормальной системы Ax = f метод релаксации (13) сходится при любом

x (0) и любом ω ∈ (0,2) . В общем случае задача нахождения оптимального значения параметра решена, и в практических расчетах принимают метод проб и ошибок.

ω не

II. Вычисление определителей, обращение матриц. 1. Вычисление определителей. 1.1 Применение метода Гаусса. Идея способа Гаусса последовательного исключения неизвестных в системе уравнений может быть перенесена на задачу вычисления определителей, и здесь она переходит в способ последовательного понижения порядка n определителя. Рассмотрим схему единственного деления. Пусть дан определитель

a11 D=

a12 K a1n

a21 a22 K a2 n . K K K K an1 an 2 K ann

Выберем как–либо ведущий элемент первого шага преобразований. Он должен быть отличен от нуля. Иногда, чтобы избежать сильного разброса в порядках чисел, за него принимают либо наибольший по модулю элемент D , либо наибольший по модулю элемент в избранной строке или избранном столбце. Выполняя, если нужно, перестановку строк и столбцов, можно считать, что за ведущий элемент принят a11 . Вынося a11 из первой строки (первого столбца) за знак D , приведем определитель к виду

32

1 b12 a a D = a11 21 22 K K an1 an 2

K b1n K a2 n K

K

.

K ann Умножая первую строку последовательно на a21, a31, ..., an1 и вычитая из второй, третьей и т.д. строк, получим

a22(1)

a23(1) K a2 n (1)

0 a22(1) K a2 n (1) a32(1) = a11 D = a11 K K K K K

a33(1) K a3n (1) K K K

an 2(1) K ann (1)

an3(1) K ann (1)

1

b12

0

b1n

K

an 2(1)

(1)

Этим мы понизим порядок определителя на единицу и можем перейти ко второму шагу преобразований, применяя к полученному определителю порядка n − 1 такие же преобразования. Выполняя все n шагов, найдем определитель D :

D = a11 ⋅ a22(1) ⋅ a33(2) ⋅ ... ⋅ ann ( n−1)

(2)

Таким образом, для вычисления определителя нужно выполнить вычисления необходимые для осуществления прямого хода в методе Гаусса для системы Ax = 0 , а затем найти произведение ведущих элементов. Вычислительная схема в этом случае такая же, как для системы ЛАУ, только без столбца свободных членов. Контрольные соотношения остаются прежними. 1.2 Применение метода квадратных корней. Если матрица A симметрическая, то для вычисления определителя этой матрицы целесообразно использовать метод квадратных корней. Представим матрицу A в виде произведения двух взаимно транспонированных T

треугольных матриц A = T T , где

⎛ t11 t12 ⎜0 t 22 T =⎜ ⎜K K ⎜⎜ ⎝0 0 тогда det A = det T

T

K t1n ⎞ K t2 n ⎟⎟ ; K K⎟ ⎟ K tnn ⎟⎠

det T = ( det T ) = ( t11 ⋅ t22 ⋅ K ⋅ tnn ) . 2

2

Числа

tii

(i=1,2,…,n)

находим по соответствующим формулам.

t11 = a11 , t1 j =

a1 j t11

( j > 1);

i −1

2 tii = aii − ∑ tki k =1

i −1

ti j =

aij − ∑ tki tk j k =1

tii

(1 < i ≤ m), (4)

(i < j );

ti j = 0 при i > j.

2. Вычисление элементов обратной матрицы. 33

2.1 Применение метода Гаусса −1

Обратной к матрице A называют такую матрицу A , для которой

AA−1 = A−1 A = E ,

(1)

где E – единичная матрица. Квадратная матрица A называется неособенной или невырожденной, если ее определитель отличен от нуля det A ≠ 0 . Любая неособенная матрица имеет обратную. Пусть дана неособенная матрица A . Для вычисления элементов ее обратной матрицы A

−1

используем соотношение (1).

K a1n ⎞ ⎛ x11 x12 K x1n ⎞ ⎜ ⎟ K a2 n ⎟⎟ −1 ⎜ x21 x22 K x2 n ⎟ , A = ⎜K K K K ⎟ K K⎟ ⎜⎜ ⎟⎟ ⎟ K ann ⎟⎠ ⎝ xn1 xn 2 K xnn ⎠ −1 Умножая матрицу A на A и приравнивая каждый элемент произведения 2 2 соответствующему элементу матрицы E , получим систему из n уравнений с n неизвестными xij (i, j = 1, n) . Так, умножая почленно каждую строку матрицы A на первый столбец −1 матрицы A и каждый раз приравнивая полученное произведение соответствующему элементу первого столбца матрицы E , получаем систему

⎛ a11 a12 ⎜a a A = ⎜ 21 22 ⎜K K ⎜⎜ ⎝ an1 an 2

⎧a11x11 + a12 x21 + K + a1n xn1 = 1, ⎪a x + a x + K + a x = 0, ⎪ 21 11 22 21 2 n n1 ⎨ ⎪KKKKKKKKKKKK ⎪⎩an1x11 + an 2 x21 + K + ann xn1 = 0. Аналогично при почленном умножении строк матрицы A на второй столбец матрицы A

−1

образуется еще одна система

⎧a11x12 + a12 x22 + K + a1n xn 2 = 0, ⎪a x + a x + K + a x = 1, ⎪ 21 12 22 22 2n n 2 ⎨ ⎪KKKKKKKKKKKK ⎪⎩an1x12 + an 2 x22 + K + ann xn 2 = 0. 2

и т.д.

2

Таким образом, система из n уравнений с n неизвестными распадается на n систем с n неизвестными. Все эти системы имеют одну и ту же матрицу A и отличаются только свободными членами. Т.к. при решении системы по методу Гаусса основные вычисления приходится производить над матрицей коэффициентов, решение этих систем можно объединить в одной схеме, рассматривая одновременно n столбцов свободных членов. Замечание: При вычислении обратной матрицы можно использовать также метод Гаусса с выбором главного элемента. Элементы обратной матрицы получаются с некоторой погрешностью, которая появляется в результате округлений в процессе вычислений. Рассмотрим метод исправления элементов приближенной обратной матрицы. 2.2. Применение метода итераций для уточнения элементов обратной матрицы. 34

A получены приближенные значения Пусть для неособенной матрицы элементов обратной матрицы. Обозначим матрицу с такими элементами через

X 0 ≈ A−1 ;

для уточнения элементов обратной матрицы строим следующий итерационный процесс:

X k = X k −1 ( 2 E − AX k −1 )

(k = 1,2,...)

(2)

Рассмотрим матрицу

Gk = E − AX k .

(3)

Тогда (2) с учетом (3) перепишется в виде:

X k = X k −1 ( E + Gk −1 )

(k = 1,2,...)

(4)

Достаточные условия сходимости для процесса (2): Для матрицы (3) верно получаемое ниже правило уменьшения индекса k и выражение через начальное значение G0 :

Gk = E − AX k = E − AX k −1 ( E − AX k −1 ) = ( E − AX k −1 ) = Gk2−1 = Gk4−2 = ... = G02 Погрешность приближения имеет следующее выражение через G0 : 2

A−1 − X k = A−1 ( E − AX k ) = A−1Gk = A−1G02

k

k

Отсюда получается оценка

A−1 − X k ≤ A−1 ⋅ G0

2k

(5)

Поэтому можно сказать, что если приближенное значение X 0 будет настолько −1

близко к A , что

G0 = E − AX 0 < 1, то X k → A−1 ; при этом сходимость будет k

весьма быстрой, т.к. показатель степени 2 в (5) с ростом k увеличивается очень быстро. Матрица Gk на каждом шаге характеризует в некотором смысле степень −1

близости матрицы X k к матрице A . Обычно итерации продолжают до тех пор, пока элементы матрицы модулю не станут меньше заданного числа ε , и тогда приближенно полагают

Gk по

A−1 ≈ X k

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

35

III. Проблема собственных чисел Во многих задачах одновременно с матрицей A приходится рассматривать связанное с ней уравнение

A − λE =

a11 − λ a21

a12 K a22 − λ K

K

K

an1

an 2

K

a1n a2 n K

= 0,

(1)

K ann − λ

которое называют характеристическим (или вековым) уравнением матрицы A . Определитель A − λ E есть алгебраический многочлен степени n от λ со старшим коэффициентом (−1) n и его обычно записывают в виде

A − λ E = (−1) n ( λ n − p1λ n −1 − K − pn ) = (−1) n Pn ( λ ) Многочлен Pn ( λ ) называют собственным многочленом

λ1 , λ2 ,K , λn называются многочлена характеристическими числами) матрицы однородная система

(2)

матрицы A . Корни

собственными значениями (или A . Они характеризуются тем, что

Ax = λ x

(3)

имеет ненулевое решение в том и только в том случае, когда λ есть собственное значение A . Отвечающие ему ненулевые решения системы (3) получили название собственных векторов матрицы, соответствующих значению λ . Отыскание собственных значений матрицы A – это задача решения алгебраического уравнения степени n в форме (1) или (4) Pn ( λ ) = λ n − p1λ n −1 − K − pn .

(4)

После того как собственные значения будут вычислены, соответствующие им собственные векторы могут быть найдены как решение однородной системы (3). Опр. Задача нахождения собственных значений матрицы называется полной проблемой собственных значений. Существует ряд задач, где полные сведения не являются необходимыми и можно ограничиться меньшим объемом знаний: например, достаточно указать границы, в которых лежат все собственные значения, как это бывает при изучении устойчивости или неустойчивости процессов, или найти собственное значение, близкое к известному числу, когда рассматриваются явления резонанса, и т.д. Такого рода задачи называются частичными проблемами собственных значений и для каждой из них создаются свои методы решения. 1. Решение полной проблемы собственных чисел. Прямые методы. 1.1 Метод Данилевского (для матриц с небольшой размерностью). Сведение матрицы A преобразованием подобия к канонической форме Фробениуса Ф: ⎛ p1 p2 p3 K pn −1 pn ⎞ ⎜ ⎟ 0⎟ ⎜1 0 0 K 0 Ф=⎜ 0 1 0 K 0 0⎟ ⎜ ⎟ ⎜K K K K K K ⎟ ⎜0 0 0 K 1 0 ⎟⎠ ⎝

36

Преобразование B = S −1 AS матриц B и A с помощью невырожденной матрицы S называется преобразованием подобия. Известно, что подобное преобразование матрицы A не изменяет ее собственного многочлена: B − λ E = S −1 AS − λ S −1 ES = S −1 ⋅ A − λ E ⋅ S = A − λ E , где λ – собственное значение матрицы B (и матрицы A ). Пусть y – собственный вектор матрицы B , соответствующий λ : By = λ y . By = S −1 AS y = λ y

(1)

A( S y) = λ ( S y)

Таким образом, мы доказали, что у двух подобных матриц собственные значения одинаковы (т.е. при преобразовании подобия собственные значения не меняются), а собственные векторы получаются один из другого умножением на матрицу, которая осуществляет преобразования подобия. Запишем характеристический многочлен матрицы в канонической форме Фробениуса p1 − λ p2 p3 K pn −1 pn p2 p3 K pn −1 pn −λ 0 K 0 1 0 1 −λ K 0 0 n −1 Ф − λE = 0 = 1 −λ K 0 0 = ( p1 − λ )( −λ ) − K K K K K K K K K K K −λ 0 0 K 1 −λ 0 0 0 K 1 = ( p1 − λ )( −λ )

n −1

= ( p1 − λ )( −λ )

n −1

− p2 ( −λ )

n−2

− p2 ( −λ )

n−2

+

p3

p4

pn −1

pn

1

−λ K

0

0

K 0

K K 0 K

K 1

K −λ

+ p3 ( −λ )

K

n −3

− K + ( −1)

n +1

=K

pn =

= ( −1) ( λ n − p1λ n −1 − p2λ n − 2 − K − pn ) = ( −1) Pn ( λ ) n

n

В преобразовании Ф = S −1 AS матрицу S целесообразно находить путем последовательного приведения строк к каноническому виду. 1-й шаг. Начнем с приведения последней строки. Предположим, что элемент an n −1 ≠ 0 . Разделим на него ( n − 1) -й столбец матрицы A . Вновь полученный ( n − 1) -й

столбец умножим на ani и вычтем из столбца номера i . Проделав это для

i = 1, 2,K , n − 2, n , приведем последнюю строку к виду Фробениуса. Такое преобразование равносильно умножению матрицы A справа на матрицу 0 0 0 ⎞ K ⎛ 1 ⎜ ⎟ 1 0 0 ⎟ K ⎜ 0 ⎜ K K K K K ⎟ M n −1 = ⎜ ⎟ an 2 ann ⎟ 1 ⎜ − an1 − K − ⎜ an n −1 an n −1 an n −1 an n −1 ⎟ ⎜⎜ ⎟⎟ 0 0 0 1 K ⎝ ⎠ 1 ≠ 0 , следовательно, существует обратная матрица: Определитель M n −1 = an n −1

37

0 K 0 0 ⎞ ⎛ 1 ⎜ ⎟ 1 K 0 0 ⎟ ⎜ 0 M −1 = ⎜ K K K K K⎟ n−1 ⎜ ⎟ ⎜ an1 an 2 K an n −1 ann ⎟ ⎜ 0 0 K 0 1 ⎟⎠ ⎝ Этим заканчивается 1-й шаг преобразования. В результате получим матрицу 1 1 ⎛ a11 a12 K a11 n −1 a11n ⎞ ⎜ ⎟ K K K K K ⎟ −1 ⎜ . A1 = M A M = 1 n−1 n−1 ⎜ an −11 a1n−12 K a1n −1 n −1 a1n −1 n ⎟ ⎜⎜ ⎟ K 0 1 0 ⎟⎠ ⎝ 0 2-й шаг преобразований аналогичен первому и состоит в приведении предпоследней строки матрицы A1 к виду Фробениуса при условии неизменности последней ее строки. Предположим, что в

A1

элемент

a1n −2 n −1 ≠ 0 . Нужное

преобразование можно записать в форме

A2 =

M n−2

M −1 A1 n−2

M

1 ⎛ ⎜ 0 ⎜ ⎜ K ⎜ = ⎜ a1n −11 ⎜ − a1 ⎜ n −1 n − 2 ⎜ 0 ⎜⎜ 0 ⎝

n−2

=

M −1 n−2

0 0 K

K K K K − K K

M −1 n−1

AM

n−1

0 0 K

a1n −1 n −3

1

a1n −1 n − 2

a1n −1 n − 2

0 0

0 0

M n−−12

M

0 ⎛ 1 ⎜ 1 ⎜ 0 ⎜ K K =⎜ 1 1 ⎜ an −11 an −12 ⎜ 0 0 ⎜⎜ 0 ⎝ 0

n−2

2 ⎛ a11 ⎜ ⎜ K = ⎜ an2−21 ⎜ ⎜ 0 ⎜ 0 ⎝

K

a12n − 2

a12n −1

K

K

K

K

1

0

K

0

1

K an2− 2 n − 2

an2−2 n −1

a12n ⎞ ⎟ K ⎟ an2− 2 n ⎟ ⎟ 0 ⎟ 0 ⎟⎠

⎞ ⎟ ⎟ ⎟ ⎟ a1n −1 n −1 a1n −1 n ⎟ − 1 − 1 an −1 n − 2 an−1 n− 2 ⎟ ⎟ ⎟ 1 0 ⎟⎟ 0 1 ⎠ K 0 0 0 0 K K K K 1 1 K an−1 n −1 an −1 n 1 0 K 0 1 K 0 0 K

0 0 K

Правило построения матриц M n − 2 и M n−−12 по

⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟⎟ ⎠ A1 аналогично правилу

построения M n −1 и M n−−11 по A . Эта аналогия сохраняется при всех следующих шагах. n −1 ≠0, Таким образом, в регулярном случае, когда ann −1 ≠ 0, a1n −1 n − 2 ≠ 0, K , a21

после выполнения n − 1 шагов преобразований матрица A будет приведена к каноническому виду Фробениуса

38

A n −1= M 1−1 M 2−1 K M n−−11 A M n −1 M n −2 K M 1 = S −1 AS = n −1 n −1 ⎛ a11 a12 ⎜ 1 0 =⎜ ⎜ K K ⎜⎜ 0 ⎝ 0

K a1nn−−11 a1nn−1 ⎞ ⎛ p1 p2 K ⎟ ⎜ 0 0 ⎟ ⎜1 0 K K = K K K ⎟ ⎜K K K ⎟ ⎜ 1 0 ⎟⎠ ⎜⎝ 0 0 K K

По первой строке полученной матрицы Ф многочлен A : Pn ( λ ) = λ n − p1λ n −1 − ... − pn .

pn −1 pn ⎞ ⎟ 0 0⎟ =Ф K K⎟ ⎟ 1 0 ⎟⎠

составляется собственный

Требования aik+1i ≠ 0 всегда можно добиться путем перестановок строк и столбцов (обычно на это место ставят наибольший элемент в строке). Это наиболее экономичный метод, порядок операций n3 . Вычисление собственных векторов. Определив собственные значения λ i (i = 1,..., n) матрицы

A,

то

ее

собственные векторы могут быть найдены путем решения однородных систем Ax = λ i x . Но если построена матрица S , с помощью которой A приводится к виду Фробениуса Ф = S −1 AS , то нахождение собственных векторов, как было доказано выше, значительно упрощается. Так как собственные значения матриц Ф и A совпадают (т.к. эти матрицы подобны), то найдя собственные векторы матрицы Ф , легко найти собственные векторы матрицы A (см. (1)). Итак, считаем λ i (i = 1,..., n) известными. Ф = S −1 AS . Найдем собственные векторы матрицы Ф , запишем систему уравнений Фy = λ i y в развернутом виде ⎛ p1 p2 K pn −1 pn ⎞ ⎛ y1 ⎞ ⎛ y1 ⎞ ⎜ ⎟⎜ ⎟ ⎜ ⎟ y 0 K 0 0 ⎟ ⎜ y2 ⎟ ⎜1 =λ⎜ 2⎟ ⎜ K K K K K ⎟ ⎜ ... ⎟ ⎜ ... ⎟ ⎜⎜ ⎟⎟ ⎜⎜ ⎟⎟ ⎜⎜ ⎟⎟ 0 ⎠ ⎝ yn ⎠ ⎝ yn ⎠ ⎝ 0 0 K 1 В составляющих вектора y система имеет вид: p1 y1 + p2 y2 + ... + pn yn = λ i y1 , y1 = λ i y2 , ................ yn −1 = λ i yn . Так как собственный вектор находится заведомо с точностью до численного множителя, можно положить yn = 1 . Тогда все составляющие вектора y найдутся последовательно, начиная с последнего уравнения системы до первого, и для y получим y = λ in −1 , λ in − 2 ,..., λ i , 1

(

)

Первое уравнение системы (2) приведется к равенству p1λ in −1+ p2 λ in − 2 + ... + pn = λ in и будет удовлетворяться, т.к. λ i есть корень собственного многочлена Pn (λ ) матрицы A. В регулярном случае (см. выше) для матрицы S получается представление вида

39

S = M n−1 M n− 2 ...M 1 . Умножая S на собственный вектор y , получим для собственного вектора x матрицы А выражение x = Sy = M n −1 M n − 2 ...M 1 y Каждая матрица M i (i=1,…,n-1) отличается от единичной матрицы только одной строкой. При умножении вектора на M i будет изменяться только одна составляющая вектора. Поэтому в полученном выражении вектора x удобно y умножать на M 1 , M 2 ,... последовательно. Пример. Задана матрица ⎛ a11 a12 a13 ⎞ ⎛ 2 1 1 ⎞ ⎜ ⎟ ⎜ ⎟ A = ⎜ a21 a22 a23 ⎟ = ⎜ 3 2 1 ⎟ ⎟ ⎜a ⎟ ⎜ ⎝ 31 a32 a33 ⎠ ⎝ 1 2 2 ⎠ Найти собственные числа и собственные векторы методом Данилевского. Решение: ⎛ p11 p12 p13 ⎞ ⎜ ⎟ −1 Ф = S AS , Ф=⎜ 1 0 0 ⎟ ⎜ 0 1 0 ⎟⎠ ⎝ Матрицу S находим путем последовательного приведения строк к каноническому виду, начиная с последней строки. Считаем, что ann −1 ≠ 0 . Разделим на

него (n-1)-й столбец матрицы A . Вновь полученный ( n − 1) -й столбец умножим на ani и вычтем из столбца номера i . Проделав это для i = 1, 2,K , n − 2, n , приведем последнюю строку к виду Фробениуса. Такое преобразование равносильно умножению матрицы A справа на матрицу ⎛ 1 0 0 ⎞ ⎛ 1 0 0⎞ ⎜ ⎟ ⎟ a31 a33 ⎟ ⎜⎜ 1 1 1 ⎜ − = − −1⎟ , det M 2 = 0,5 ≠ 0 ⇒ ∃ M 2 −1 M n −1 = M 2 = − ⎜ a32 a32 ⎟ a32 ⎟ ⎜ 2 2 ⎜⎜ ⎟⎟ ⎜ 0 0 1 ⎟ 0 1 ⎠ ⎝ ⎠ ⎝ 0 0 0 ⎞ ⎛1 0 0⎞ ⎛ 1 ⎜ ⎟ ⎜ ⎟ −1 M 2 = ⎜ a31 a32 a33 ⎟ = ⎜ 1 2 2 ⎟ ⎜ 0 0 1 ⎟⎠ ⎜⎝ 0 0 1 ⎟⎠ ⎝

⎛ 1 ⎛ 2 1 1⎞⎜ ⎜ ⎟ 1 AM 2 = ⎜ 3 2 1 ⎟ ⎜ − ⎜1 2 2⎟⎜ 2 ⎝ ⎠⎜ 0 ⎝

0 1 2 0

0⎞ ⎟ ⎛ 2 − 0,5 0,5 −1 + 1 ⎞ ⎛ 1,5 0,5 0 ⎞ ⎜ ⎟ ⎜ ⎟ 1 −2 + 1 ⎟ = ⎜ 2 1 −1 ⎟ −1⎟ = ⎜ 3 − 1 ⎟ ⎜ 1−1 1 −2 + 2 ⎟⎠ ⎜⎝ 0 1 0 ⎟⎠ 1 ⎟⎠ ⎝

0,5 0⎞ ⎛ 1 0 0 ⎞ ⎛1,5 0,5 0 ⎞ ⎛ 1,5 ⎜ ⎟⎜ ⎟ ⎜ ⎟ A1 = M 2 AM 2 = ⎜ 1 2 2 ⎟ ⎜ 2 1 −1⎟ = ⎜ 1,5 + 4 0,5 + 2 + 2 −2 ⎟ = ⎜0 0 1⎟⎜ 0 1 0 ⎟⎠ ⎜⎝ 0 1 0 ⎟⎠ ⎝ ⎠⎝ 1 1 1 ⎛ 1,5 0,5 0 ⎞ ⎛ a11 a12 a13 ⎞ ⎟ ⎜ ⎟ ⎜ = ⎜ 5,5 4,5 −2 ⎟ = ⎜ a121 a122 a123 ⎟ 1 1 1 ⎟ ⎜ 0 1 0 ⎟⎠ ⎜⎝ a31 a32 a33 ⎝ ⎠ −1

40

−1

A2 = M 1 A1M 1 ⎛ 1 a123 ⎞ ⎛ 1 a122 4,5 2 ⎞ − − − ⎜ 1 1 1 ⎟ ⎜ a21 a21 ⎟ 5,5 5,5 5,5 ⎟ ⎜ a21 ⎜ ⎟ M1 = ⎜ 0 1 0 ⎟=⎜ 0 1 0 ⎟ ⎜ ⎟ 0 1 ⎟ ⎜⎜ 0 0 1 ⎟⎟ ⎜ 0 ⎟ ⎜ ⎟ ⎜⎝ ⎠ ⎝ ⎠ ⎛ a121 a122 a123 ⎞ ⎛ 5,5 4,5 −2 ⎞ ⎜ ⎟ ⎜ ⎟ M 1−1 = ⎜ 0 1 0 ⎟=⎜ 0 1 0⎟ ⎜ 0 0 1 ⎟⎠ ⎜⎝ 0 0 1 ⎟⎠ ⎝ 4,5 2 ⎞ ⎛ 1,5 4,5 3 ⎞ ⎛ 1 − −1,5 ⋅ + 0,5 ⎜ ⎟ ⎜ 5,5 5,5 5,5 5,5 5,5 ⎟ ⎛ 1,5 0,5 0 ⎞ 5,5 ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ 1 0 ⎟=⎜ 1 2 − 2⎟ = A1M 1 = ⎜ 5,5 4,5 −2 ⎟ ⎜ 0 −4,5 + 4,5 ⎜ 0 1 0 ⎟⎠ ⎜⎜ 0 0 1 ⎟⎟ ⎜⎜ 0 1 0 ⎟⎟ ⎝ ⎜ ⎟ ⎜ ⎟ ⎝ ⎠ ⎝ ⎠ 4 3 ⎞ ⎛ 1,5 ⎜ 5,5 − 5,5 5,5 ⎟ ⎜ ⎟ 0 0 ⎟ =⎜ 1 ⎜ 0 1 0 ⎟⎟ ⎜ ⎜ ⎟ ⎝ ⎠ 4 3 ⎞ ⎛ 1,5 − ⎜ 5,5 5,5 ⎟ ⎛ 1,5 + 4,5 −4 − 2 3 ⎞ ⎛ 6 −6 3 ⎞ ⎛ 5,5 4,5 −2 ⎞ 5,5 ⎜ ⎟ ⎜ ⎜ ⎟ ⎟ ⎜ ⎟ A 2 = M 1−1 A1M 1 = ⎜ 0 1 0 ⎟⎜ 1 0 0 ⎟=⎜ 1 0 0⎟ = ⎜ 1 0 0⎟ = Ф ⎜ 0 0 1 ⎟⎠ ⎜⎜ 0 1 0 ⎟⎟ ⎜⎝ 0 1 0 ⎟⎠ ⎜⎝ 0 1 0 ⎟⎠ ⎝ ⎜ ⎟ ⎝ ⎠

Т.к. Фy = λ i y −6 y1 + 6 y2 − 3 yn = λ i y1 , y1 = λ i y2 , y2 = λ i y3 . Так как собственный вектор находится заведомо с точностью до численного множителя, можно положить y3 = 1 . Тогда все составляющие вектора y найдутся последовательно, начиная с последнего уравнения системы до первого, и для y получим y = λ i2 , λ i , 1

(

)

По первой строке полученной матрицы Ф составляется собственный многочлен матрицы А: Pn (λ ) = λ n − p1λ n −1 − ... − pn = λ 3 − 6λ 2 + 6λ − 3 = 0 Получили нелинейное уравнение, корни которого можно найти методом Ньютона или методом простой итерации для нелинейных уравнений. 1.2 Итерационный метод вращений для решения полной проблемы собственных чисел.

41

Этот метод применим к для эрмитовым матрицам с комплексными элементами, но для простоты рассмотрим действительные симметричные матрицы. Идея в преобразовании матриц к диагональной форме Любую симметричную действительную матрицу можно привести к диагональному виду преобразованием подобия

A = U ΛU −1 ,

(2)

где U – ортогональная матрица ( UU = E ) и Λ – диагональная, элементами которой T

являются собственные значения

λ 1 , ... , λ n матрицы A . Так как для ортогональной −1

матрицы обратная совпадает с транспонированной ( U = U ), то (2) равносильно T

U T AU = Λ

(3)

Формула (3) дает возможность построить много алгоритмов для приближенного вычисления матрицы Λ , отличающиеся между собой способами построения матрицы U. Для использования равенства (3) нужно построить последовательность ортогональных преобразований, позволяющих неограниченно уменьшать модули недиагональных элементов матрицы A (т.е. стремиться получить в итоге матрицу Λ ). Рассмотрим один из алгоритмов, а именно метод вращений, т.к. он достаточно прост по вычислительной схеме и обладает быстрой сходимостью– это итерационный процесс, где на каждом шаге осуществляется такое преобразование подобия, что

(U

T 1

AU1

)

ij

= 0 – наибольший недиагональный элемент по абсолютной величине

обращается в 0. В качестве U1 выбирается матрица вращения. Т.к. матрица симметричная, то достаточно рассмотреть элементы выше главной диагонали.

⎡1 ⎤ ⎢ O ⎥ 0 ⎢ ⎥ ⎢ ⎥ 1 ⎢ ⎥ cos ϕ K − sin ϕ ⎢ ⎥ K (i ) ⎥ U1 = U i j (ϕ ) = ⎢ M O M ⎢ ⎥ sin ϕ K cos ϕ ⎢ ⎥K( j ) ⎢ ⎥ 1 ⎢ ⎥ 0 O ⎥ ⎢ ⎢⎢ 1⎥⎥⎦ ⎣

A

(4)

Опред. Вещественные матрицы, отличающиеся от единичной матрицы, четырьмя элеметами, расположенными на пересечении строк и столбцов с номерами i, j и имеющими вид (4) (где в общем случае определения вместо cos ϕ может стоять c и ниже ± c , аналогично вместо − sin ϕ стоять − s , и т.п., где

c 2 + s 2 = 1 ) называются матрицами вращения, в которой угол ϕ определяется из условия, что наибольший недиагональный элемент после преобразования подобия =0 Обозначим

B1 = AU1 , B1 = ⎡⎣bi j ⎤⎦

j -тый столбец произведения

42

b 1 j = a 1i( − sin ϕ ) + a1 j cos ϕ b 2 j = a 2i( − sin ϕ ) + a 2 j cos ϕ

(5)

b kj = a ki( − sin ϕ ) + a kj cos ϕ i

....

j

⎡1 ⎤ ⎢ O ⎥ 0 ⎢ ⎥ ⎢ ⎥ 1 ⎢ ⎥ i⎢ cos ϕ K sin ϕ ⎥ K (i ) −1 −1 ⎥ U1 = U i j (ϕ ) = ⎢ M O M ⎢ ⎥ − sin ϕ K cos ϕ ⎢ ⎥K( j ) ⎢ ⎥ 1 ⎢ ⎥ O ⎥ 0 ⎢ ⎢⎢ 1⎥⎥⎦ ⎣ Наибольший

недиагональный

( ) = (U

−1 1 AU1

(1)

приравниваем нулю A

элемент

ij

)

после

преобразования

подобия

= cos ϕ ⋅ bij + sin ϕ ⋅ b jj = 0

ij

Подставляем в это выражение из (5) значение bij и получаем

(

)

(

)

cos ϕ aii ( − sin ϕ ) + aij cos ϕ + sin ϕ a ji ( − sin ϕ ) + a jj cos ϕ = 0 2 aii − a jj sin ϕ cos ϕ 2 2a ji 2a ji 1 tg 2ϕ = ⇒ ϕ = arctg aii − a jj 2 aii − a jj

aij cos 2ϕ =

(

)

ϕ – угол при котором максимальный недиагональный элемент

Таким образом

(1)

обратился в 0. Получили новую матрицу A (1)

A

= U1−1 AU1

.

– 1-ый шаг закончен. (1)

2-й шаг – повторение предыдущего по отношению к матрице A . Таким образом, по заданной матрице A будем строить последовательность (k )

матриц A (k )

( k +1)

такую, что каждая следующая матрица A

получается из предыдущей

A преобразованием подобия со следующей ортогональной матрицей вращения (или матрица поворота осей i, j на угол ϕ ): A(

k +1)

= U k−1 A( )U k k

Для исследования сходимости введем меру отклонения матрицы диагональной: t ( A) =

∑

i, j i≠ j

aij2

A от

.

Верно равенство (если использовать t ( A) =

∑

i, j i≠ j

aij2 и расписать) 43

(

) (

) ( )

t A( k +1) = t A( k ) − 2 aij( k ) Что происходит с мерой отклонения за 1 шаг (k ) (k ) Пусть aij = max aml – наибольший m ,l:m≠l

2

(6)

недиагональный элемент и он

(

( k +1)

предполагается отличным от 0, верно неравенство t A

(

)

) < t(A ), (k )

и мера

t A( k ) уменьшается при переходе к A( k +1) . Что касается скорости стремления A( k ) к k

0, то по выбору элемента aij справедливо неравенство

(

)

( )

t A( k ) ≤ n(n − 1) aij( k ) Т.к. в сумме

∑ aml2

n(n − 1)

содержится

2

(n > 2)

слагаемых

(7)

( )

2 , aij aml

2

= max ( aml ) m ≠l

2

Это

m ≠l очевидное неравенство (n>2 иначе метод вращения к матрице второго порядка нечего и применять).

Из (7) следует

(a ) (k ) ij

2

≥

(

t A( k )

)

(8)

n(n − 1)

С помощью этого неравенства (8) из (6) получается

(

) (

) ( )

t A( k +1) = t A( k ) − 2 aij( k )

2

(

)

≤ t A( k ) −

(

)

(

)

2 t A( k ) = qt A( k ) , n ( n − 1) 1 424 3

<1, т.к. n>2

q =1−

2 n(n − 1)

при этом 0 ≤ q<1 ввиду n ≥ 2 . Отсюда возникает цепь неравенств

(

)

(

)

(

)

( )

t A( k ) ≤ qt A( k −1) ≤ q 2t A( k −2) ≤ K ≤ q k t A(0) , (0)

и т.к. A

(

(

)

= A , то для t A( k ) будем иметь оценку

)

t A( k ) ≤ q k t ( A )

(

(k )

Отсюда вытекает, что t A

) → 0 (k → ∞)

Таким образом

A( ) = U k−1....U 2−1U1−1 AU1 U 2 ...U k → Λ k

k →∞

Следовательно, сходимость метода вращения мы доказали. Буем считать, что при

(U

−1

k

1 A( k ) ≈ Λ ,

а

последовательность

матриц

U1 U 2 ...U k → U

)

k →∞

AU = Λ . Итак, будем считать, что нашли матрицу U , с помощью которой матрицу A можно преобразовать к диагональной. Как решается проблема собственных чисел у диагональной матрицы:

44

⎛0⎞ ⎛ 0 ⎞ ⎜0⎟ ⎜ 0 ⎟ ⎜ ⎟ ⎜ ⎟ Λei = Λ ⎜ M ⎟ = ⎜ M ⎟ = λ i ei ⎜ ⎟ ⎜ ⎟ ⎜1⎟ i ⎜λ i ⎟ ⎜0⎟ ⎜ 0 ⎟ ⎝ ⎠ ⎝ ⎠

⎛ λ1 0 ... 0 ⎞ ⎜ 0 λ ... 0 ⎟ 2 ⎟, Λ=⎜ ⎜ ... ... ... ... ⎟ ⎜⎜ ⎟⎟ ⎝ 0 0 0 λn ⎠

λi , но мы получили приближение к

Собственные числа матрицы A –

(k )

диагональной матрице отсюда следует, что собственные числа матрицы A – aii , что (k )

собственные векторы матрицы A – Uei ⇔ aii

⎛ u11 u12 ⎜u u Uei = ⎜ 21 22 ⎜ ... ... ⎜⎜ ⎝ un1 un 2

≈ λi aii( k )

... u1n ⎞ ⎛ 0 ⎞ ⎛ u1i ⎞ ... u2 n ⎟⎟ ⎜⎜ 0 ⎟⎟ ⎜⎜ u2i ⎟⎟ = ... ... ⎟ ⎜ 1 ⎟ i ⎜ ... ⎟ ⎟⎜ ⎟ ⎜ ⎟ ... unn ⎟⎠ ⎝ 0 ⎠ ⎜⎝ uni ⎟⎠

То есть i-тому собственному числу будет соответствовать i-тый столбец матрицы U (определяющий собственный вектор). Пример: Найти собственные числа и собственные векторы матрицы А методом вращения.

⎛ cos ϕ U1 = ⎜⎜ sin ϕ ⎜ 0 ⎝

⎛ 3 2 1 ⎞ i =1 A = ⎜⎜ 2 3 1 ⎟⎟ ⎜ 1 1 3⎟ ⎝ ⎠

tg 2ϕ = ⎛ ⎜ ⎜ U1 = ⎜⎜ ⎜ ⎜⎜ ⎝

2aij aii − a jj 1 2 1 2 0

−

=

1 2 1 2 0

⎛ ⎜ ⎛ 3 2 1⎞ ⎜ AU1 = ⎜⎜ 2 3 1 ⎟⎟ ⎜⎜ ⎜ ⎟ ⎝ 1 1 3⎠ ⎜ ⎜ ⎜ ⎝

− sin ϕ cos ϕ 0

0 ⎞ i =1 0 ⎟⎟ –матрица вращения осей i j 1 ⎟⎠ (i = 1, j = 2)

π 2⋅2 = ∞ ⇒ϕ = 3−3 4 ⎞ 0⎟ ⎟ ⎟ 0⎟ ⎟ 1⎟ ⎟ ⎠ 1 2 1 2 0

⎛ 1 ⎜ 2 ⎜ T U1 = ⎜⎜ − 1 2 ⎜ ⎜⎜ 0 ⎝ −

1 2 1 2 0

⎞ ⎛ 3+ 2 0⎟ ⎜ ⎟ ⎜ 2 ⎟ ⎜ 2+3 0⎟ = ⎜ 2 ⎟ ⎜ 1⎟ ⎜ 2 ⎟ ⎜ ⎠ ⎝ 2

1 2 1 2 0

⎞ 0⎟ ⎟ ⎟ 0⎟ ⎟ 1⎟ ⎟ ⎠

⎞ ⎛ 5 −3+ 2 1⎟ ⎜ 2 ⎟ ⎜ 2 ⎟ ⎜ 5 −2 + 3 1⎟ = ⎜ 2 ⎟ ⎜ 2 ⎟ ⎜ 2 0 3⎟ ⎜ ⎠ ⎝ 2

−1 2 1 2 0

⎞ 1⎟ ⎟ ⎟ 1⎟ ⎟ ⎟ 3⎟ ⎠

45

⎛ 1 ⎜ 2 ⎜ T AU1 AU1 = ⎜⎜ − 1 2 ⎜ 0 ⎜ ⎜ ⎝

⎛ ⎜ A =⎜ 1 ⎜2 ⎝

2⎞

2

5

0

0

1

0

0

3

2

⎞⎛ 0⎟ ⎜ ⎟⎜ ⎟⎜ 0⎟ ⎜ ⎟⎜ 1⎟ ⎜ ⎟⎜ ⎠⎝

1 2 1 2 0

5 2 5 2 2 2

i =1

⎟ ⎟ ⎟ ⎠

−1 2 1 2 0

⎞ 1⎟ ⎟ ⎟ 1⎟ ⎟ ⎟ 3⎟ ⎠

⎛ 5+5 ⎜ ⎜ 2 = ⎜⎜ −5+5 ⎜ 2 ⎜ 2 ⎜ ⎝ 2

⎛ cos ϕ U =⎜ 0 2 ⎜ ⎜ sin ϕ ⎝

−1+1 2 1+1 2 0

0

2 ⎞ ⎟ 2⎟ ⎟ 0 ⎟ ⎟ 3 ⎟⎟ ⎠

⎛ ⎜ ⎜ =⎜ ⎜ ⎜ ⎜ ⎝

5

0

0 2 2

1 0

2 ⎞ ⎟ 2⎟ 0 ⎟ ⎟ 3 ⎟⎟ ⎠

− sin ϕ ⎞ i = 1

1 0

⎟ ⎟ ⎟ cos ϕ ⎠ j = 3 0

(i=1,j=3)

2 2 2⋅ 2aij 2 = 2 = 2 = 2 tg 2ϕ = = 5−3 2 aii − a jj 2 1 ϕ = arctg 2 ≈ 0, 4777658 ⇒ 27o37′ 2 cos(0,4777658...) ≈ 0,89 sin(0,4777658...) ≈ 0,46 2⋅

0,892 + 0,462 = 0,7921 + 0, 2116 = 1,0037 – погрешность округления 2 ⎞ ⎛ i =1 5 0 ⎜ ⎟ ⎛ cos ϕ 0 − sin ϕ ⎞ i = 1 2 ⎜ ⎟ ⎜ A1 = ⎜ 0 1 0 ⎟ U2 = ⎜ 0 1 0 ⎟⎟ ⎜ 2 ⎟ ⎜ sin ϕ 0 cos ϕ ⎟ j = 3 ⎝ ⎠ ⎜⎜ ⎟ 0 3 ⎟ ⎝ 2 ⎠ ⎛ 5 0 1,41⎞ ⎛ 0,89 0 −0,46 ⎞ ⎛ 5⋅0,89+1,41⋅0,46 0 −5⋅0,46+1,41⋅0,89 ⎞ ⎛ 5,1 0 −1,05 ⎞ ⎜ ⎟⎜ ⎟ ⎜ ⎟ ⎜ ⎟ AU 1 0 ⎟=⎜ 0 1 0 1 0 ⎟ ⎟≈⎜ 0 1 2 = ⎜ 0 1 0 ⎟⎜ 0 ⎜1,41 0 3 ⎟ ⎜ 0,46 0 0,89 ⎟ ⎜ 1,41⋅0,89+3⋅0,46 0 −1,41⋅0,46+3⋅0,89 ⎟ ⎜ 2,63 0 2,02 ⎟ ⎝ ⎠⎝ ⎠ ⎝ ⎠ ⎝ ⎠

U 2−1 AU 1 2

⎛ 0,89 0 0,46 ⎞ ⎛ 5,1 0 −1,05 ⎞ = ⎜⎜ 0 1 0 ⎟⎟ ⎜⎜ 0 1 0 ⎟⎟ = ⎜ −0,46 0 0,89 ⎟ ⎜ 2,63 0 2,02 ⎟ ⎝ ⎠⎝ ⎠

⎛ 0,89⋅5,1+ 0,46⋅2,63 0 −0,891,05 ⋅ + 0,46⋅2,02 ⎞ ⎛ 5,7488 0 −0,0053 ⎞ ⎜ ⎟ ⎜ ⎟ 0 1 0 0 1 0 ⎟ = A2 ⎜ ⎟=⎜ ⎜ −0,46⋅5,1+ 0,89⋅2,63 0 −0,46⋅( −1,05)+ 0,89⋅2,02 ⎟ ⎜ −0,0053 0 2,2808 ⎟ ⎝ ⎠ ⎝ ⎠

Видно, что с увеличением итераций недиагональные элементы стремятся к 0. λ1 ≈ 5,7488 λ 2 ≈ 1 λ 3 ≈ 2,2808 – приближенные собственные значения матрицы А Мера отклонения

( ) ( 2)

t A

2

2 = ∑ ⎡ aij( ) ⎤ = 2 ⋅ 0,00532 = 5,6 ⋅ 10−5 ⎣ ⎦ i≠ j

2. Частичная проблема собственных чисел – это нахождение либо (чаще) максимальных по модулю значений СЧ, либо (реже) минимальных по модулю.

46

= A1

Все методы решения частичной проблемы собственных чисел являются итерационными. Определение наибольшего по модулю собственного значения. Предположим, что матрица А имеет n-линейно-независимых собственных векторов Напомним, что v v Ae = λ ⋅ e , (*) r где e – собственный вектор линейного оператора А, λ – собственное число Пусть СЧ расположены в порядке убывания:

λ1 ≥ λ2 ≥ .... ≥ λn r r e2 .... en – СВ

r e1

Итерационный метод нахождения

1) Возьмем векторов:

x (1) = Ax (0) ,

λ max

x (0) – произвольный вектор и образуем последовательность x (2) = Ax (1) ,...., x ( k ) = Ax ( k −1)

Ax (0) = A (α1e1 + .... + α nen ) = { α1 Ae1 + ... + α n Aen = { α1λ1e1 + ... + α nλ nen лин

СЗ

Разложим по СВ (т.е. по системе линейно-независимых векторов)

x (0) = α1e1 + α 2e2 + ... + α nen x (1) = Ax (0) = α1λ1e1 + α 2λ 2e2 + ... + α nλ nen ........................................................................ x ( k ) = Ax ( k −1) = α1λ1k e1 + α 2λ 2k e2 + ... + α nλ nk en Идея основана на том, что λ1 – наибольшее Отметим, что x

(i )

ei , i = 1,k – векторы, но знак вектора мы опускаем. Запишем s – тую компоненту (отличную от 0) (ограничение α1 ≠ 0, e1s ≠ 0 ) и

xs ( k ) = α1λ1k e1s + α 2λ 2k e2 s + ... + α nλ nk ens xs ( k +1) = α1λ1k +1e1s + α 2λ 2k +1e2 s + ... + α nλ nk +1ens n

xs

( k +1)

xs ( k )

=

∑αiλik +1eis i =1 n

∑αiλik eis

⎧⎪1 α1λ1k e1s ⎫⎪ 1 + μ 2k +1γ 2 s + μ3k +1γ 3s + ... + μ nk +1γ ns =⎨ ⎬ = λ1 k 1 1 + μ 2kγ 2 s + ... + μ nkγ ns α λ e ⎩⎪ 1 1 1s ⎭⎪

i =1

где

μi =

λi αe , γ is = i is λ1 α1e1s

а) Рассмотрим случай

λ1 > λ2 ≥ .... ≥ λn . Тогда все μi < 1 при достаточно

больших k подчеркнутая дробь будет близка к 1. Получаем приближенное максимальное СЧ:

xs ( k +1) xs ( k )

≈ λ1 (k >> 1)

47

Замечание: независимость отношения

xs ( k +1) xs ( k )

от s (т.е. координат) служит

основанием для выбора к >>1. Чтобы найти СВ надо рассмотреть равенство: k x( ) = α1λ1k e1 + α 2λ 2k e2 + .... + α nλ nk en k x( )

λ1k

= α1e1 + α 2 μ 2k e2 + .... + α n μ nk en

μi < 1 (k >> 1) можно получить приближенное равенство

В случае, когда

e1 ≈

x(k )

λ1k

– СВ, множитель

α1 можно опустить, т.к. СВ определяются с точностью до

константы (до множителя) б) λ1 = λ2 = .... = λr >

xs ( k +1) xs ( k )

=

λr +1 ≥ λr + 2 .... .

α1λ1k +1e1s + .... + α r λ rk +1ers + α r +1λ rk++11er +1s + ... α1λ1k e1s + .... + α r λ rk ers + α r +1λ rk+1er +1s + ... k +1

k +1

Разделим и числитель и знаменатель на число: α1λ1 e1s + .... + α r λ r ers Получим:

xs ( k +1) xs

(k )

= λ1

1 + μ rk++11 γ r/ +1 s + .... 1+

μ rk+1 γ r/ +1 s (k )

(NB! Выбираем xs

+ ...

,

μi =

λi , λ1

λ1k x(k )

λ1k

α i eis

α1e1s + .... + α r ers

≠ 0 , предполагаем α1e1s + .... + α r ers ≠ 0 )

Аналогично предыдущему случаю: получаем

x(k )

γ i/ s =

xs ( k +1) xs ( k )

≈ λ1 (k >> 1)

= α1e1 + α 2e2 + ... + α r er + μ rk+1er +1 + ... 14243 →0 при k →∞

≈ α1e1 + α 2e2 + ... + α r er – линейная комбинация собственных векторов ( 0)

В качестве начальных x берем r раз независимых вектора, получаем систему линейных независимых уравнений, откуда получаем e1, e2 , e3 в) Пусть λ1 = −λ2 .

xs (2 k ) = α1λ12 k e1s + α 2λ 22 k e2 s + α 3λ32 k e3s + ... (одинаковые знаки при четном номере)

xs (2 k + 2) = α1λ12 k + 2e1s + α 2λ 22 k + 2e2 s + α 3λ32 k + 2e3s + ...

48

xs (2 k + 2) xs (2 k )

=

α1λ12 k + 2e1s + α 2λ12 k + 2e2 s + α 3λ32 k + 2e3s + ... α1λ12 k e1s + α 2λ12 k e2 s + α 3λ32 k e3s + ...

=

14442444 3 λ12 =λ22

α 3λ32 k + 2e3s + + .... α1λ12 k e1s + α 2λ12 k e2 s

λ12 =

1+

α 3λ32 k e3s + ... α1λ12 k e1s + α 2λ12 k e2 s

1 + μ32 k +2γ 3// + ... 1 + μ32 kγ 3// + ...

λi α i eis , γ i// = λ1 α1e1s + α 2e2 s

μi =

xs (2 k + 2) xs

= λ12

(2 k )

= λ12 отсюда получаем два СЗ: λ1 = −λ2

Для СВ:

x (2 k )

λ12 k

= α1e1 + α 2e2 + α 3μ32 k e3 + ... 14243 →0 k →∞ μ3<1

x (2 k )

≈ α1e1 + α 2e2

λ12 k

( 2 k +1)

Аналогично расписываем для xs

x (2 k +1)

Получаем:

λ12 k +1

≈ α1e1 − α 2e2

Два уравнения – два неизвестных СВ III. Решение нелинейных уравнений. 1. Случай одного уравнения. Исследование уравнения Пусть функция f ( x) действительного переменного. Требуется найти корни уравнения

f ( x) = 0

(1)

на заданном сегменте [ a, b ] . Относительно функции f ( x)

будем предполагать, что

она есть любая кусочно-непрерывная функция действительного аргумента, которая на [ a, b] непрерывна и имеет кусочно-непрерывную производную. Уравнение (1) называется алгебраическим, если заданная функция есть полином n -й степени:

f ( x) = P( x) = a0 x n + a1x n−1 + K + an−1x + an = 0, Всякое x

неалгебраическое

уравнение

(1)

называется

a0 ≠ 0

(2)

трансцендентным,

2

например, e − x + 10 = 0; x − tg x = 0 . Алгебраические и трансцендентные конечных уравнений, в отличие от уравнения получили общее название дифференциальных, интегральных, ур-й в частных производных и т.д. 49

Задача решения уравнения (1) совпадает с задачей определения корней (или нулей) функции f ( x ) . Число x = ξ называется корнем функции f ( x ) , если f (ξ ) ≡ 0 . Число ξ корнем k-й кратности, если при x = ξ вместе с функцией обращаются в нуль и все производные до k-1 порядка включительно. Если k=1, корень называют простым. При определении приближенных значений корней уравнения (1) необходимо решить две задачи: 1) отделение корней, т.е. определение достаточно малых промежутков в каждом из которых заключен один и только один корень уравнения (простой или кратный). 2) уточнение корней с наперед заданным числом верных знаков. При условии f ′(ξ ) ≠ 0 задача отделения корня x = ξ всегда возможна. Отделение корней можно производить графически и аналитически. При графическом отделении корней уравнение (1) надо преобразовать к виду

ϕ1 ( x) = ϕ2 ( x)

(3)

и построить графики функций

y1 = ϕ1 ( x); Корнями уравнения (1)

y2 = ϕ 2 ( x )

(4)

f ( x) = ϕ1 ( x) − ϕ2 ( x) = 0

являются абсциссы точек пересечения этих графиков Если ϕ 2 ( x) = 0 , то искомые корни уравнения (1) есть точки пересечения графика функции y = f ( x) с осью абсцисс. В общем случае при построении графиков (4) следует выявить прежде всего поведение каждой из функций ϕ1 ( x) и ϕ 2 ( x) при x → −∞, x → +∞ , найти значения x при которых обычно проще всего вычисляются значения любой функции. Полезно также, если это не требует значительных вычислений, определить (можно грубо) точки минимума и максимума функций (4). Из аналитических методов отделения корней укажем только два общих метода пригодных как для алгебраических так и для трансцендентных уравнений. Один из них – нахождение более простого уравнения, которое имеет корни, приблизительно равные искомым корням данного уравнения. Это можно сделать пренебрегая в данном уравнении малыми членами. При втором методе используются следующие теоремы, непосредственно вытекающие из свойств непрерывных функций. Теорема 1. Если функция действительного аргумента f ( x) непрерывна на сегменте [ a, b ] и на его концах значения f ( a ) и f (b) имеют противоположные

знаки, то между точками a и b имеется хотя бы один действительный корень уравнения f ( x) = 0 .

Если при этом f ( x ) имеет первую производную, не меняющую знака на [ a, b ] ,

т.е. если f ( x) на [ a, b ] меняется монотонно, то корень единственный. Теорема 2.

Пусть f ( x ) есть аналитическая функция переменного x на

сегменте [ a, b ] ; если на концах [ a, b ] она принимает значения разных знаков, то

между точками a и b имеется нечетное число корней уравнения f ( x) = 0 ; если же

на концах [ a, b ] она принимает значения одинаковых знаков, то между точками a и

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

50

Алгебраическое уравнение n -й степени (2) всегда имеет точно n корней (действительных или комплексных), что вытекает из Теорема Гаусса. Полином степени n имеет точно n действительных корней или комплексных корней, если каждый k -кратный корень считать k раз. Теорема Безу. Остаток от деления полинома Р(х) на двучлен (х-а) равен Р(а), т.е. значению этого полинома при x=a. (теорема Безу справедлива и в комплексной области). В частности, если все коэффициенты полинома Р(х) – действительные числа, то корни уравнения Р(х)=0 могут быть только действительными или комплексно сопряженными. Число действительных корней алгебраического уравнения (2) с действительными коэффициентами равно или на четное число меньше степени уравнения. Теорема Декарта. Число положительных корней равно (или на четное число меньше) числу перемен знака в ряду коэффициентов уравнения.. Если в уравнении (2) a0 > 0 (этого всегда можно достичь, поменяв при отрицательном a0 все знаки в левой части уравнения), то его действительные корни удовлетворяют неравенству Маклорена, определяющему верхнюю границу корней:

x <1+ m

A , a0

(5)

где m – индекс первого отрицательного коэффициента в ряду a0 , a1 ,..., an ; А – максимальный из модулей отрицательных коэффициентов. Эта же оценка позволяет установить и нижнюю границу корней. Для этого n

следует сделать замену x = − y и умножить полученное уравнение на ( −1) , для того чтобы старший коэффициент остался положительным, после чего снова воспользоваться формулой (5). Замечание: При исследовании алгебраических уравнений следует иметь в виду следующую их особенность. Наличие на графике полинома Y = P ( x ) каждого минимума, при котором P ( x ) положительно, и каждого максимума с отрицательным значением P( x) свидетельствует о наличии у этого полинома пары комплексных корней. Так полином, график которого изображен на рис.1, имеет по крайней мере, три пары комплексных корней, о чем свидетельствует форма графика полинома в окрестности точек А, В, С.

Рис. 1.

51

Эти особенности (или условия) не принадлежат к необходимым условиям, а являются только достаточными, т.е. график может не иметь ни одной точки из рассматриваемых типов, а уравнение может иметь несколько пар комплексных корней (см. пример 1 из практич. занятия). После того как исследование уравнения (1) закончено и для каждого действительного корня ξ установлен интервал в котором этот корень находится, переходим к решению второй задачи – к уточнению найденных корней. Отделение корня ξ , т.е установление двойного неравенства a < ξ < b уже дает возможность получить его грубое приближенное значение, в качестве которого можно взять центр интервала ( a, b ) :

ξ1 =

a+b . 2

При этом абсолютная погрешность будет меньше числа

ε<

a −b . 2

Подставив найденное ξ1 в уравнение (1) и убедившись, что оно не обеспечивает требуемую точность, принимаем f (ξ1 ) = a1 или f (ξ 2 ) = b1 и в результате приходим к одному из следующих, более точных неравенств: a1 < ξ < b или a < ξ < b1 , так что продолжая этот процесс, можем произвести уточнение корня с любой наперед заданной степенью точности. (Метод деления отрезка пополам). Теория алгебраических уравнений разработана значительно полнее уравнений трансцендентных. Поэтому последние часто пытаются свести к уравнениям алгебраическим. В частности это можно сделать, разложив левую часть заданного трансцендентного уравнения f ( x) = 0 в степенной ряд

f ( x) = c0 + c1x + c2 x 2 + ... + cn x n + ..., где ck =

1 (k ) f (0); k = 0,1,2,... k!

(*)

Рассмотрим последовательность алгебраических уравнений, получающихся, если приравнять нулю частичные суммы ряда (*):

c0 + c1x = 0; c0 + c1x + c2 x 2 = 0; ..................................

(**)

c0 + c1x + c2 x 2 + ... + cn x n = 0. Пусть ξ1 – корень первого из этих уравнений, ξ 2 – один из корней второго уравнения, ξ n – один из корней n-го уравнения. Тогда имеет место следующая теорема

Если последовательность ξ1, ξ 2 ,..., ξ n сходится и предел этой последовательности ξ принадлежит области, в которой ряд (*) сходится к функции f (ξ ) , то число ξ является корнем уравнения f ( x) = 0 . Из этой теоремы следует, что вместо трансцендентного уравнения f ( x) = 0 можно попытаться решить несколько уравнений последовательности (**). Если среди Теорема 3.

52

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

2 x9 + x 7 − x 4 + 19 x3 − 24 x 2 + 2 = 0 .

(*)

Решение: Уравнение имеет нечетное число действительных корней, но не больше девяти. Число перемен знаков в ряду его коэффициентов равно четырем, поэтому согласно теореме Декарта положительных корней может быть четыре, два или ни одного. Выполнив замену x = − y и поменяв знаки на обратные, получаем

2 y 9 + y 7 + y 4 + 19 y 3 + 24 y 2 − 2 = 0 ,

(**)

поэтому в исходном уравнении (*) есть только один отрицательный корень. Границы действительных чисел найдем, воспользовавшись неравенством (5). Для исходного уравнения (*), учтя, что a1 = a3 = a4 = 0, a5 = −1 , имеем

m = 5 ; A = 24 ; a0 = 2 , следовательно, все его положительные корни удовлетворяют

неравенству

x <1+ 5

24 = 1 + 5 12 ≈ 2,6 2

Аналогично для преобразованного уравнения (**), у которого знак изменяет только свободный член a9 = −2 , получаем

y <1+ 9

2 = 2, 2

откуда x = − y > −2 . Таким образом, корни исходного уравнения лежат в интервале

−2 < x < 2,6 Результаты проведенного исследования легко проверить непосредственно, построив график рассматриваемого полинома (**) (см. рис.2).

Рис. 2.

y = P( x) = 2 x9 + x 7 − x 4 + 19 x3 − 24 x 2 + 2 ,

(***)

53

а более точные значения минимального и максимального действительных корней равны: x1 = −0,262364; x3 = 1,029626 . Уравнение (***) имеет еще три пары комплексных корней, хотя на графике нет ни одной точки из рассмотренных в замечании типов. Пример 2. Вычислить положительный корень уравнения. f ( x) ≡ x 2 − sin 5 x = 0 с точностью до 0,00001. Решение: 1) отделение корней Графическое отделение искомого корня. Строим графики функций y = x 2 , y = sin 5 x

π

= 0, 628... 5 В качестве исходного отрезка возьмем отрезок [ 0,5; 0, 6] , для чего прежде всего

Из рисунка видно, что положительный корень лежит между 0,5 и проверяем знаки на концах отрезка f (0,5) = 0, 25 − sin 2,5 = 0, 25 − 0, 6 < 0 f (0, 6) = 0,36 − sin 3, 0 = 0,36 − 0,14 > 0

Т.е. по теореме 1 (занятие 15) на [ 0,5; 0, 6] имеется хотя бы один действ. корень. Далее проверяем сохранение знака у производных f ′( x) = 2 x − 5cos 5 x > 0 при 0,5 < x < 0, 6 f ′′( x) = 2 + 25sin 5 x > 0 при 0,5 < x < 0, 6 Т. е. точек минимума и максимума и перегиба на этом отрезке нет 2) уточнение корней – можно применить метод деления отрезка пополам. Отделение корня ξ , т.е установление двойного неравенства a < ξ < b уже дает возможность получить его грубое приближенное значение, в качестве которого можно взять центр интервала ( a, b ) :

a+b . 2 При этом абсолютная погрешность будет меньше числа a −b ε< . 2 Подставив найденное ξ1 в уравнение (1) и убедившись, что оно не обеспечивает требуемую точность, принимаем f (ξ1 ) = a1 или f (ξ 2 ) = b1 и в результате приходим к одному из следующих, более точных неравенств: a1 < ξ < b или a < ξ < b1 , так что продолжая этот процесс, можем произвести уточнение корня с любой наперед заданной степенью точности. (Метод деления отрезка пополам).

ξ1 =

54

Искомый корень лежит в интервале: 0,56365 < ξ < 0,56366 2. Итерационные методы вычисления изолированного корня уравнения f ( x) = 0 . Введение Такие методы предполагают указания какой-либо области D , содержащий этот единственный корень. Если f ( x) – непрерывна, то вещественный корень принадлежит любому отрезку, на концах которого, функция имеет значения разных знаков. Деля отрезок пополам получаем универсальный метод вычисления корня (метод бисекции). Этот подход не требует знания хорошего начального приближения. Если оно имеется, то для гладких функций используются более эффективные методы. Пусть отыскивается единственный на [ a, b ] корень z уравнения f ( x) = 0 в

предположении непрерывности функции f ( x ) . Итерационный метод решения порождает последовательность приближений { xn } , которая сходится к корню: lim xn − z = 0 . Величину en = xn − z называют n→∞

абсолютной ошибкой на n -й итерации. Итерационный метод имеет порядок m (или скорость сходимости m ), если m есть наибольшее положительное число, для которого существует такая конечная постоянная q > 0 , что

lim sup

n→∞

Постоянную

en+1 ≤ q < ∞. enm

q называют константой асимптотической ошибки, она обычно

(

оценивается через производные функции f ( x) в точке x = z . При m = 1 q ∈ ( 0,1)

)

сходимость называется линейной (метод сходится со скоростью геометрической прогрессии со знаменателем q ), при 1 < m < 2 – сверхлинейной, при m = 2 – квадратичной и т.д. 2.1 Метод секущих Если имеется хорошее приближение к корню x = z уравнения

f ( x) = 0 ,

(1)

Простейший вариант метода: в процессе итераций фиксируется некоторая точка x0 , приближение xn+1 находится как абсцисса точки пересечения прямой проходящей через точки ( x0 , f ( x0 ) ) и ( xn , f ( xn ) ) с осью x (рис. 1).

Рис. 1.

Рис. 2.

xn+1 принимается абсцисса точки пересечения с осью x прямой, проходящей через точки ( xn−1, f ( xn−1 ) ) и ( xn , f ( xn ) ) . Обычно более эффективен способ, где за

Уравнение этой прямой 55

yn ( x) = f ( xn ) + ( x − xn )

f ( xn ) − f ( xn−1 ) . xn − xn−1

Из условия yn ( xn+1 ) = 0 получаем расчетную формулу

xn+1 = xn −

f ( xn )( xn − xn−1 ) f ( xn ) − f ( xn−1 )

2.2 Метод хорд (метод ложного положения) Пусть f ( a ) f (b) < 0 идея метода состоит в замене кривой y = f ( x) хордами, проходящими через концы отрезков, в которых, f ( x) имеет противоположные знаки. В методе хорд требуется , чтобы один конец отрезка, на котором ищется корень, был неподвижен. В качестве такого неподвижного конца x0 выбирают тот конец отрезка

для которого знак f ( x) совпадает со знаком f ′′( x ) . Расчетная формула имеет вид

xn+1 = xn −

f ( xn ) ( xn − x0 ) f ( xn ) − f ( x0 )

2.3 Метод Ньютона или метод касательных Пусть PAQ дуга кривой y = f ( x) (рис.1), которая пересекает ось Ох в точке А, так что абсцисса x = ξ точки А есть корень уравнения

f ( x) = 0

(1)

Допустим, что дуга АР обращена выпуклостью к оси Ох. Проведем через точку Р с координатами ( x0 ; y0 = f ( x0 ) ) касательную к кривой y = f ( x) . Угловой коэффициент касательной равняется значению производной от функции f ( x) в точке касания; k = f ′( x0 ) ; следовательно, уравнение касательной , которая проходит через точку P( x0 , y0 ) будет

y − y0 = f ′( x0 ) ⋅ ( x − x0 )

(2)

Отсюда положив в (2) y = 0,

y0 = f ( x0 ) , находим точку пересечения касательной с осью абсцисс (y=0), которую обозначим через x1 f ( x0 ) x1 = x0 − f ′( x0 )

56

Рис. 1.

Через точку P1 ( x1; y1 = f ( x1 ) ) снова проводим касательную и, продолжая этот процесс, приходим к формуле Ньютона

xn+1 = xn −

f ( xn ) ; n = 0,1,2,..., f ′( xn )

(3)

Значения x0 , x1, x2 ,... , вычисленные по формуле (3), образуют последовательность , которая стремится к значению корня уравнения (1). Если мы начнем процесс, исходя из точки Q , в которой кривая обращена к оси Ох вогнутостью, то первый же шаг приведет на другую сторону от оси Ох, где кривая обращена к ней выпуклостью, так что в дальнейшем будем приближаться к значению корня так же , как и прежде В тех случаях, когда вычисление второй производной для функции f ( x ) не ведет к существенным усложнениям, можно указать критерий , который поможет проверить правильность выбора начального значения x0 . Действительно, т.к. кривая y = f ( x) обращена выпуклостью к оси Ох в тех случаях для которых выполняется соотношение

f ( x) ⋅ f ′′( x) > 0

(4)

то этому условию и должно удовлетворять выбранное значение x0 . Установим связь между погрешностями n-го и n+1 шага. Согласно формуле Тейлора имеем

f (ξ ) = f ( xn ) + f ′( xn )(ξ − xn ) + где точка cn лежит между xn и ξ . Т.к. f (ξ ) = 0 , то отсюда получаем

ξ − xn +

1 f ′′(cn )(ξ − xn ) 2 , 2

f ( xn ) 1 f ′′(cn ) 2 ξ − xn ) , =− ⋅ ( f ′( xn ) 2 f ′( xn )

но согласно формуле (3)

xn −

f ( xn ) = xn+1 . f ′( xn )

Следовательно, 57

1 f ′′(cn ) 2 ξ − xn ) , ( 2 f ′( xn )

ξ − xn+1 = − ⋅ откуда и находим следующую оценку

M 2 ξ − xn ) , ( 2 f ′( xn )

ξ − xn+1 ≤

(5)

где М – наибольшее значение f ′′( x) в рассматриваемой окрестности корня ξ . Оценка (5) показывает, что при вычислении корня по методу Ньютона погрешность каждого нового приближения уменьшается пропорционально квадрату погрешности предыдущего приближения. Таким образом, в тех случаях когда в рассматриваемой окрестности искомого корня величина

M не слишком велика, то сходимость f ′( xn )

метода достаточно быстрая (каждое новое приближение удваивает число верных десятичных знаков) и наоборот. Т.о. представление об истинном значении величины

M в каждом конкретном примере можно получить, проанализировав рост числа f ′( xn ) верных знаков в 2-х 3-х предыдущих шагах. Если в предыдущих шагах число верных знаков с ростом n примерно удваивалось, то это подтверждает , что величина

M f ′( xn )

мала и метод Ньютона целесообразно применять. 2.4 Метод простой итерации Применение метода итераций требует предварительного приведения уравнения f ( x) = 0 к каноническому виду

x = ϕ ( x)

(1)

Область изменения аргумента x на числовой оси назовем X (отрезок числовой оси). Область значений функции y = ϕ ( x) обозначим Y . Функцию ϕ можно рассматривать как оператор, преобразующий X в Y.

Рис.1

Построим график обеих частей уравнения (1): для левой части: прямая линия y = x – биссектриса первого координатного угла, для правой части – некоторая линия с уравнением y = ϕ ( x) (обозначим буквой l ). Решением уравнения является абсцисса x * точки М* пересечение l и биссектрисы. 58

Допустим, что для x * имеется начальное приближение x0 . В простейшем методе итерации все дальнейшие приближения строятся по формуле

xn+1 = ϕ ( xn ), n = 0,1,...

(2)

Этот процесс называется одношаговой итерацией. Геометрическое значение процесса вычислений xn указано на рисунке 1. По x0

находится на l точка M 0 [ x0 ,ϕ ( x0 )] , через нее проводится прямая параллельная оси х и находится точка ее пересечения с биссектрисой. Абсцисса этой точки принимается за следующее приближение x1 к x * и т.д. Рассмотрим поведение приближений xn , когда они находятся вблизи x * .

Для этого рассмотрим их погрешности

ε n = xn − x * . Зависимость между ε n и ε n+1

получится,

xn

если

в

(2)

вместо

xn = x * +ε n , xn+1 = x * +ε n+1 :

и

xn+1

подставить

их

выражения

x * +ε n+1 = ϕ ( x * +ε n ) = ϕ ( x*) + ε nϕ ′( x*) + o(ε n ) Если воспользоваться равенством x* = ϕ ( x*) и пренебречь малой величиной более высокого порядка малости o(ε n ) , то зависимость между ε n и ε n+1 запишется в виде приближенного равенства 1. Когда ϕ ′( x*) > 1, погрешность

ε n+1 > ε n и приближение xn+1 будет

отстоять от x * дальше, чем xn . Решение x * будет “точкой отталкивания” для приближений xn , близких к нему, и в этом случае не будет сходимости последовательности xn к x * . 2.

Если ϕ ′( x*) < 1 , то погрешность

ε n+1 < ε n и можно ожидать, что

последовательность xn , если x0 взято достаточно близким к x * , будет сходится к x * приблизительно со скоростью геометрической прогрессии со знаменателем q = ϕ ′( x) .

ϕ ′ ( x *) > 0 ε n+1 и ε n будут иметь одинаковые знаки, и сходимость xn к x * будет монотонной. Если ϕ ′ ( x *) < 0 , то погрешности ε n+1 и ε n имеют разные При

знаки, и приближение xn будет сходиться к x * , колеблясь около x * .

ϕ ′( x*) = 0 требует специального рассмотрения, так как тогда ε n+1 будет малой величиной высшего порядка сравнительно с ε n . Поэтому, если x0 взято 3. Случай

достаточно близким к x * , то xn будет весьма быстро сходится к x * : при возрастании

n погрешность

ε n будет стремиться к нулю со скоростью, превосходящей

сходимость геометрической прогрессии со сколь угодно малым знаменателем. Это часто используют для ускорения сходимости последовательности xn к x * путем преобразования заданного уравнения (1) к новому x = ψ ( x) , имеющему то же решение x * , но такому, что ψ ′ ( x*) = 0 Укажем порядок малости ε n+1 сравнительно с ε n . Пусть ϕ непрерывную производную порядка m вблизи x * , и выполняются равенства

имеет

ϕ ′( x*) = ... = ϕ ( m−1) ( x*) = 0 и ϕ ( m ) ( x*) ≠ 0 В этом случае разложение ϕ ( xn ) = ϕ ( x * +ε n ) около x * будет иметь форму 59

ϕ ( xn ) = ϕ ( x * +ε n ) = ϕ ( x *) + Подстановка его в (2) и отбрасывание o между

( )

1 ( m) ϕ ( x *) ε nm + o ε nm m!

(ε ) даст следующее соотношение m n

ε n+1 и ε n : ε n+1 ≈

1 ( m) ϕ ( x *) ε nm . m!

Отсюда видно, что ε n+1 будет малой величиной порядка m относительно Теорема 1. О сходимости итерационной последовательности: Пусть выполняются условия: 1) функция ϕ ( x) определена на отрезке

x − x0 ≤ δ ,

(4)

εn .

(5)

непрерывна там и удовлетворяет условию Липшица с постоянным коэффициентом, меньшим единицы:

ϕ ( x) − ϕ ( x′) ≤ q x − x′

( 0 ≤ q < 1) ;

(6)

2) для исходного приближения x0 верно неравенство

x0 − ϕ ( x0 ) ≤ m ; 3) числа

δ , q, m удовлетворяют условию m ≤δ . 1− q

(7)

Тогда 1) уравнение (1) в области (5) имеет решение; 2) последовательность xn приближений, построенная по правилу (2), принадлежит отрезку (5), является сходящейся ( lim xn = x *) , и предел

последовательности x * удовлетворяет уравнению (1); 3) скорость сходимости xn к x *

x * − xn ≤

m n q , 1− q

n = 1,2,...

(8)

Поясним условия теоремы: Функция ϕ преобразует отрезок

x0 − δ ≤ x ≤ x0 + δ числовой оси в некоторый отрезок той же оси. Возьмем две точки x, x′ на [ x0 − δ , x0 + δ ] . Расстояние между ними есть x − x′ , а Отношение

ϕ ( x) − ϕ ( x′) x − x′

ϕ ( x) − ϕ ( x′) есть расстояния между их изображениями. есть коэффициент увеличения этих расстояний при

преобразовании. По условию (6) он не превосходит числа q , но т.к. q <1, то при отображении оператором ϕ происходит не растяжение, а сжатие всех отрезков с коэффициентом, не большим q . Входящая в условие величина m связана с близостью начального приближения x0 к решению x * . Если окажется, что x0 = x * и, тогда, x0 − ϕ ( x0 ) = 0 , то можно 60

считать m =0. Когда x0 ≠ x * , но x0 близко к x * , то разность x0 − ϕ ( x0 ) будет иметь малое значение, и m может быть взята малой величиной. Неравенство (7) налагает на δ , q, m ограничение достаточное для того, чтобы были верны утверждения теоремы 1. Теорема 2. О единственности решения На всяком множестве точек, где для функции

ϕ ( x) выполняется условие

ϕ ( x) − ϕ ( y ) < x − y , x ≠ y , уравнение x = ϕ ( x) может иметь не более одного решения.

Пример. Найдем по методу итераций с пятью значащими цифрами наименьший положительный корень уравнения

1 cos x − sin x = 0 x

(1*)

Решение Заменим уравнение (1*) эквивалентным ему уравнением

x = tg x , и построив графики функций y1 = x, что можно взять

x0 =

(2*)

y2 = tg x (сделать самостоятельно) находим, 3π ≈ 4,7 2

Однако, к уравнению (2*) непосредственно метод итераций применить нельзя, т.к. при любом значении x

ϕ ′( x) = (tg x)′ =

1 ≥1 cos 2 x

То есть условие пункта 2 не удовлетворяется. Поэтому перейдем к обратной функции, т.е. к уравнению

x = arctg x ,

(3*)

для которого

ϕ ′( x) = (arctg x)′ =

1 < 1 при 1 + x2

x ≠ 0.

Уравнение (3*), которое эквивалентно исходному (1*) решаем при помощи формулы

xn+1 = arctg xn , где

x0 = 4,7

Итерационный процесс заканчиваем тогда, когда с необходимой точностью совпадут значения xn , xn+1 . Выполнив вычисления, приведенные в таблице, получаем x = 4,4934 . n 0 1 2 3 4,7 4,50 4,494 4,4934 xn

arctg xn

4,50

4,494

4,4934

4,4934 61

3. Метод простой итерации для системы двух уравнений Пусть дана система двух уравнений с двумя неизвестными: ⎧ F1 ( x, y ) = 0, ⎨ ⎩ F2 ( x, y ) = 0,

(1)

действительные корни которых требуется найти с заданной степенью точности. Предположим, что система (1) допускает лишь изолированные корни. Число этих корней и их приближенные значения можно установить, построив кривые F1 ( x, y ) = 0, F2 ( x, y ) = 0 и определив координаты точек их пересечения . Для применения метода итерации система (1) приводится к виду ⎧ x = ϕ1 ( x, y ), ⎨ ⎩ y = ϕ 2 ( x, y ).

(2)

Функции ϕ1 ( x, y ), ϕ 2 ( x, y ) называются итерирующими. Алгоритм решения задается формулами ⎧⎪ xn +1 = ϕ1 ( xn , yn ), ⎨ ⎪⎩ yn +1 = ϕ 2 ( xn , yn )

( n = 0,1, 2,...) ,

(3)

где x0 , y0 – некоторое начальное приближение. Теорема Пусть в некоторой замкнутой окрестности R ( a ≤ x ≤ A, b ≤ y ≤ B ) имеется одно и только одно решение x = ξ , y = η системы (2). Если 1) функции ϕ1 ( x, y ), ϕ 2 ( x, y ) определены и непрерывно дифференцируемы в R, 2) начальные приближения x0 , y0 и все последующие приближения xn , yn (n=1,2,…) принадлежат R. 3) в R выполнены неравенства ⎧ ∂ ϕ1 ∂ ϕ 2 + ≤ q1 < 1, ⎪ ∂x ⎪ ∂x ⎨ ⎪ ∂ ϕ1 + ∂ ϕ 2 ≤ q < 1, 2 ⎪ ∂y ∂y ⎩

(4)

то процесс последовательных приближений (3) сходится к решению x = ξ , y = η системы, т.е. lim xn = ξ и lim yn = η . n →∞

n →∞

Эта теорема остается верной, если условие (4) заменить условием (4’). ⎧ ∂ ϕ1 ∂ ϕ1 + ≤ q1 < 1, ⎪ ∂y ⎪ ∂x ⎨ ⎪ ∂ ϕ 2 + ∂ ϕ 2 ≤ q < 1, 2 ⎪ ∂x ∂y ⎩

(4’)

Оценка погрешности n-го приближения дается неравенством M ξ − xn + η − yn ≤ ( xn − xn−1 + yn − yn−1 ) , 1− M

62

где М – наибольшее из чисел q1 , q2 , входящих в неравенства (4) или (4’). M Сходимость метода итераций считается хорошей, если М<1/2, при этом < 1 , так 1− M что если в двух последовательных приближениях совпадают, например, первые три десятичных знака после запятой, то ошибка последнего приближения не превосходит 0,001. (См. на практике пример 1) Построение итерирующих функций для системы (1) Для преобразования системы (1) к виду (2) с соблюдением условия (4) используем следующий прием. Положим ϕ1 ( x, y ) = x + α F1 ( x, y ) + β F2 ( x, y ),

ϕ 2 ( x, y ) = y + γ F1 ( x, y ) + δ F2 ( x, y ) (αδ ≠ βγ ) . Коэффициенты α , β , γ , δ найдем как приближенные решения следующей системы уравнений: ∂ F1 ( x0 , y0 ) ∂ F2 ( x0 , y0 ) ⎧ +β = 0, ⎪1 + α ∂x ∂x ⎪ ∂ F2 ( x0 , y0 ) ⎪ ∂ F1 ( x0 , y0 ) +β = 0, ⎪α ∂y ∂y ⎪ ⎨ ⎪γ ∂ F1 ( x0 , y0 ) + δ ∂ F2 ( x0 , y0 ) = 0, ⎪ ∂x ∂x ⎪ ⎪1 + γ ∂ F1 ( x0 , y0 ) + δ ∂ F2 ( x0 , y0 ) = 0. ⎪⎩ ∂y ∂y

(5)

При таком выборе параметров условие (4) будет соблюдено, если только частные производные функций F1 ( x, y ), F2 ( x, y ) изменяются не очень быстро в окрестности ( x0 , y0 ) . (См. пример 2) Пример 1. Найти положительные корни с тремя верными знаками для системы: x 3 + y 3 − 6 x + 3 = 0, x 3 − y 3 − 6 y + 2 = 0.

Решение: Для применения метода итерации запишем данную систему в таком виде: x3 + y3 1 x= + ≡ ϕ 1( x , y ), 6 2 3 3 1 x −y + ≡ ϕ 2 ( x , y ), y= 6 3 Рассмотрим квадрат 0 ≤ x ≤ 1, 0 ≤ y ≤ 1 . Если точка ( x 0 , y 0 ) находится в этом квадрате, то имеем 0 < ϕ 1( x 0 , y 0 ) < 1 и 0 < ϕ 2 ( x 0 , y 0 ) < 1 .

Так как 0 < ( x 03 + y 03 ) 6 < 1 3 , − 1 6 < ( x 03 − y 03 ) 6 < 1 6 , то при любом выборе точки ( x 0 , y 0 ) последовательность ( x k , y k ) остается в квадрате. Более того, точки ( x k , y k ) остаются в прямоугольнике 1/2<x<5/6, 1/6
63

∂ ϕ1 ∂ ϕ1 x 2 y 2 25 36 + 1 4 34 + = + < = <1 ∂x ∂y 2 2 2 72 ∂ ϕ2 ∂ ϕ2 x2 y2 34 + = +− < <1 ∂x ∂y 2 2 72 Следовательно, существует единственное решение в указанном прямоугольнике и оно может быть найдено методом итераций. Полагая x 0 = 1 2 , y 0 = 1 2 , будем иметь 1 0,19615 1 1 8+1 8 = 0,542, = 0,533, x1 = + x2 = + 2 6 2 6 1 1 8−1 8 1 0,1223 = 0,333, = 0,354. y1 = + y2 = + 3 6 3 6 Продолжая этот процесс получим x 3 = 0,533, x 4 = 0,532, y 3 = 0,351, y 4 = 0,351 . Так как здесь q1 = q 2 = 34 72 < 0,5 , то совпадение первых трех десятичных знаков свидетельствует о достижении требуемой точности. Таким образом, можно принять ξ = 0,532, η = 0,351 . Замечание. Вместо рассмотренного на лекции итерационного процесса (3) иногда удобнее пользоваться так называемым процессом Зейделя: x n +1 = ϕ 1( x n , y n ), y n +1 = ϕ 2 ( x n +1 , y n ) (n = 0,1,2,...) Пример 2 Выбрать подходящие итерирующие функции ϕ 1( x , y ), ϕ 2 ( x , y ) при для системы уравнений x 0 = 0,8, y 0 = 0,55 : x 2 + y 2 − 1 = 0, x 3 − y = 0.

Решение: Будем искать функции ϕ 1( x , y ), ϕ 2 ( x , y) в виде

ϕ 1( x , y ) = x + α ( x 2 + y 2 − 1) + β ( x 3 − y ),

ϕ 2 ( x , y ) = x + γ ( x 2 + y 2 − 1) + δ ( x 3 − y ). Для определения параметров α , β , γ , δ составим систему (5)(см. лекции). Имеем ∂ F1 ∂ F1 ( x 0 , y 0 ) ∂ F1 ∂ F1 ( x 0 , y 0 ) = 2 x, = 1,6, = 2 y, = 11 ,, ∂x ∂x ∂y ∂y ∂ F2 ∂ F2 ( x 0 , y 0 ) ∂ F2 ∂ F2 ( x 0 , y 0 ) = 3x 2 , = 1,92, = −1, = −1. ∂x ∂x ∂y ∂y Отсюда получаем систему

1 + 1,6α + 1,92 β = 0, ,α − 11

β = 0, 1,6γ + 1,92δ = 0, , γ − δ = 0. 1 + 11 Решая, получим Таким образом ,

α ≈ −0,3, γ ≈ −0,5, β ≈ −0,3, δ ≈ 0,4 ϕ 1( x , y ) = x − 0,3( x 2 + y 2 − 1) − 0,3( x 3 − y )

ϕ 2 ( x , y ) = y − 0,5( x 2 + y 2 − 1) + 0,4( x 3 − y ) Упражнения: 1. Найти для системы положительные корни с тремя верными знаками

64

2 x 2 − xy − 5x + 1 = 0, x + 3 lg x − y 2 = 0 Ответ: x = 3,487, y = 2,262 2. Найти корни системы 2 x 2 − xy − y 2 + 2 x − 2 y + 6 = 0,

y − x −1= 0 расположенные в области , ограниченной прямыми y = 0, y = x , x = 0,5 Ответ: x=1,000, y=2,000. 4. Итерационные методы для системы с n нелинейными уравнениями. 4.1 Метод простой итерации

Пусть дана система нелинейных уравнений вида: ⎧ x1 = ϕ1 ( x1 , x2 ,..., xn ), ⎪ x = ϕ ( x , x ,..., x ), ⎪ 2 2 1 2 n ⎨ ⎪................................. ⎪⎩ xn = ϕ n ( x1 , x2 ,..., xn ),

(1)

где функции ϕ1 , ϕ 2 ,..., ϕ n действительны и определены в некоторой окрестности ω

изолированного решения ( x1∗ , x2∗ ,..., xn∗ ) этой системы, или в более компактной записи:

x = φ(x) ,

(2)

⎛ x1 ⎞ ⎛ ϕ1 (x) ⎞ ⎜ ⎟ ⎜ x2 ⎟ ϕ 2 (x) ⎟⎟ ⎜ ⎜ где x = . , φ(x) = ⎜ ... ⎟ ⎜ .... ⎟ ⎜⎜ x ⎟⎟ ⎜⎜ ϕ (x) ⎟⎟ ⎝ n⎠ ⎝ n ⎠ Для нахождения вектор-корня иногда можно использовать метод итераций x ( p +1) = φ(x ( p ) )

( p = 0,1, 2,...)

(3)

Если система уравнений задана в общем виде

f ( x) = 0 ,

(4)

где f (x) – вектор-функция, определенная и непрерывная в окрестности ω изолированного вектор-корня x∗ , то ее записывают в эквивалентном виде (2), где φ(x) – итерирующая вектор-функция, которую ищут в виде φ(x) = x + Λf (x) . Матрица Λ выбирается так Λ = − W −1 (x(0) ) . Предполагается, что матрица W(x (0) ) – неособенная.

65

⎛ ∂ f1 ⎜∂x ⎜ 1 ⎜ ∂ f2 ⎜∂x W (x) = ⎜ 1 ⎜ ... ⎜ ⎜ ∂ fn ⎜∂x ⎝ 1

∂ f1 ∂ x2 ∂ f2 ∂ x2 ... ∂ fn ∂ x2

∂ f1 ⎞ ∂ xn ⎟ ⎟ ∂ f2 ⎟ ... ⎛∂ f ∂ xn ⎟⎟ = ⎜ i ⎜∂x ... ... ⎟ ⎝ j ⎟ ∂ fn ⎟ ... ∂ xn ⎟⎠ ...

⎞ ⎟⎟ ⎠

(5)

Подставив φ(x) в (3) , получим итерационную формулу x( p +1) = x( p ) + Λf (x ( p ) )

(6)

Удобно использовать аналог метода Зейделя. ⎧ x1( k +1) = ϕ1 ( x1( k ) , x2 ( k ) ,..., xn ( k ) ), ⎪ ( k +1) ( k +1) (k ) (k ) = ϕ 2 ( x1 , x2 ,..., xn ), ⎪ x2 ⎨ ⎪................................. ⎪ x ( k +1) = ϕ ( x ( k +1) , x ( k +1) ,..., x ( k ) ), n 1 2 n ⎩ n 4.2 Метод Ньютона. Рассматриваем нелинейную систему уравнений ⎧ f1 ( x1 , x2 ,..., xn ) = 0, ⎪ f ( x , x ,..., x ) = 0, ⎪ 2 1 2 n ⎨ ⎪............................... ⎪⎩ f n ( x1 , x2 ,..., xn ) = 0

(1)

с действительными левыми частями. Более компактная запись (1): r r r r F(x) = ( f1 ( x ) , f 2 ( x ) ,..., f n ( x ) ) = 0 (2) r Пусть F(x) – оператор, отображающий линейное нормированное пространство Х на линейное нормированное пространство У. Линейный оператор, действующий из r r пространства Х в пространство У, назовем производной оператора F(x) в точке x , если r r r r r r F(x + h) − F(x) − F′(x) h = o h (3)

( )

Y

r при h

X

X

→0, ⎛ ∂ f1 ⎜ ∂x ⎜ 1 ⎜ ∂ f2 r ⎜ F′(x) = ⎜ ∂ x1 ⎜ ... ⎜ ⎜ ∂ fn ⎜ ∂x ⎝ 1

∂ f1 ∂ x2

∂ f1 ⎞ ∂ xn ⎟ ⎟ ∂ f2 ∂ f2 ⎟ ... ⎛∂ f ⎞ ∂ x2 ∂ xn ⎟⎟ = ⎜ i ⎟ (*) ⎜∂x ⎟ j ⎠ ⎝ ... ... ... ⎟ ⎟ ∂ fn ∂ fn ⎟ ... ∂ x2 ∂ xn ⎟⎠ r r r Пусть x ∗ – решение уравнения (2), x ( k ) – некоторое приближение к x ∗ . В предположении существования производной F′ , согласно (3) имеем r r r r r r r F(x ∗ ) − F(x ( k ) ) − F′(x ( k ) ) ( x ∗ − x ( k ) ) = o x ∗ − x ( k ) ,. (4) ...

Y

(

X

)

66

r r Если величина x ∗ − x ( k )

X

мала, то можно написать приближенное равенство

r r r r r F(x ( k ) ) + F′(x ( k ) ) ( x ∗ − x ( k ) ) ≈ F(x ∗ ) r Поскольку F(x ∗ ) = 0 , то r r r r F(x ( k ) ) + F′(x ( k ) ) ( x ∗ − x ( k ) ) ≈ 0 Возьмем в качестве следующего приближения решения уравнения r r r r F(x ( k ) ) + F′(x ( k ) ) ( x ( k +1) − x ( k ) ) = 0 В предположении, что оператор F′ обратим, это решение можно записать в виде (5): r r ( k +1) r ( k ) F(x ( k ) ) =x − r x , ( k = 0,1, 2,...) (5) F′ (x ( k ) )

Такой итерационный процесс называют методом Ньютона. Теорема о сходимости метода Ньютона для системы: r r r Пусть Ω a = x : x − x ∗ ≤ a – некоторое множество и в нем при некоторых

{

}

a, a1 , a2 , 0 < a, 0 ≤ a1 , a2 < ∞ выполнены условия: r r −1 r −1 r 1) ∃ F′(x), причем ∃ [ F′(x) ] , такая, что [ F′(x) ] ≤ a1 , ∀ x ∈ Ω a r r r r r r r 2 2) F(x1 ) − F(x 2 ) − F′(x 2 ) ( x1 − x 2 ) Y ≤ a2 x1 − x 2 X r r при x1 , x 2 ∈ Ω a . Обозначим c = a1a2 , b = min ( a, c −1 ) r Тогда при условиях 1), 2) и x 0 ∈ Ωb итерационный процесс Ньютона (5) сходится с оценкой погрешности: 2K r r r r x ( k ) − x ∗ ≤ c −1 c x (0) − x ∗ . # X

(

X

)

Согласно определению c, b , r r c x (0) − x ∗ < cb ≤ 1 X

Принято говорить, что метод Ньютона сходится с квадратичной скоростью, МПИ сходится со скоростью геом. прогрессии Сущность метода Ньютона. Метод применяется для уточнения найденного решения системы нелинейных уравнений , т.к. в случае систем уравнений имеются довольно жесткие условия сходимости, в силу чего МН не удается применить, когда исходное приближенное решение обладает небольшой точностью. В случае удачного нач. приближения МН обладает высокой степенью сходимости. Обычно, прежде чем применять МН, используют другой метод, который имеет слабые условия сходимости, вследствие чего в некоторых случаях требует большого кол-ва вычислений. Например, метод скорейшего спуска, обладающий важным преимуществом: неизбежной сходимости процесса. Сравнение методов решения систем нелинейных уравнений Для системы из 2-х уравнений первоначальное определение решений удобно производить графическим методом. Метод скорейшего спуска – наиболее общий метод решения систем уравнений в силу своей неизбежной сходимости, его целесообразно применять, когда МПИ и МН расходятся. (однако, если применять его для первоначального определения корней, взяв в качестве исходных данных произвольные 67

числа, то можно получить не решение системы, а значения аргумента, дающие относительный экстремум функции). МИ применяется также почти исключительно для уточнения решений. МН требует большего объема вычислений, чем МИ, но и сходится значительно быстрее при подходящем выборе нач. приближения. Пример 1. Методом Ньютона приближенно найти положительное решение системы: x2 + y 2 + z 2 = 1

2 x2 + y 2 − 4 z 2 = 0 3x 2 − 4 y + z 2 = 0 Исходя из начального приближения x0 = y0 = z0 = 0,5 Решение: Имеем ⎛ x 2 + y 2 + z 2 − 1⎞ ⎟ r ⎜ F(x) = ⎜ 2 x 2 + y 2 − 4 z 2 ⎟ , ⎜ 3x 2 − 4 y + z 2 ⎟ ⎝ ⎠ ⎛ 0, 25 + 0, 25 + 0, 25 − 1⎞ ⎛ −0, 25 ⎞ r (0) ⎜ ⎟ ⎜ ⎟ F(x ) = ⎜ 0,5 + 0, 25 − 2 ⎟ = ⎜ −1, 25 ⎟ ⎜ 0, 75 − 2 + 0, 25 ⎟ ⎜ −1 ⎟ ⎝ ⎠ ⎝ ⎠ Составим матрицу Якоби ⎛ ∂ f1 ∂ f1 ∂ f1 ⎞ ⎜ ⎟ ∂z ⎟ ⎜ ∂x ∂y ⎛ 2x r ⎜ ∂ f2 ∂ f2 ∂ f2 ⎟ ⎜ F′(x) = ⎜ ⎟ = ⎜ 4x x y z ∂ ∂ ∂ ⎜ ⎟ ⎜ 6x ⎜ ∂ f3 ∂ f3 ∂ f3 ⎟ ⎝ ⎟ ⎜⎜ ∂ x ∂ y ∂ z ⎟⎠ ⎝ ⎛1 1 r (0) ⎜ F′(x ) = F′(0,5;0,5;0,5) = ⎜ 2 1 ⎜ 3 −4 ⎝ 1 r (0) det F′(x ) = 2

1 1

2 y 2z ⎞ ⎟ 2 y −4 ⎟ −4 2 z ⎟⎠ 1⎞ ⎟ −4 ⎟ 1 ⎟⎠

1 −4 = −40

3 −4 1 Находим обратную матрицу 1 1 ⎞ ⎛ 3 ⎜ 8 8 8 ⎟ ⎛ −15 −5 −5 ⎞ ⎜ ⎟ −1 1 7 1 3 ⎟ r ⎡⎣ F′(x (0) ) ⎤⎦ = − ⎜ −14 −2 6 ⎟ = ⎜ ⎟ ⎜ 20 20 − 20 ⎟ 40 ⎜⎜ ⎟ ⎟ ⎝ −11 7 −1 ⎠ ⎜ 11 7 1 ⎟ ⎜ − ⎜ ⎟ 40 40 ⎠ ⎝ 40 Пользуясь формулой (5) из лекции, получим первое приближение

68

r x (1)

⎛ 3 ⎜ ⎛ 0,5 ⎞ ⎜ 8 −1 7 r r r ⎜ ⎟ = x (0) − ⎡⎣ F′(x (0) ) ⎤⎦ F(x (0) ) = ⎜ 0,5 ⎟ − ⎜ ⎜ ⎜ 0,5 ⎟ ⎜ 20 ⎝ ⎠ 11 ⎜⎜ ⎝ 40

1 8 1 20 7 − 40

1 ⎞ 8 ⎟ ⎛ −0, 25 ⎞ ⎟ 3 ⎟⎜ ⎟ − −1, 25 ⎟ = ⎜ ⎟ 20 ⎜ ⎟ −1 ⎟⎠ 1 ⎟⎝ ⎟ 40 ⎠

⎛ 0,5 ⎞ ⎛ 0,375 ⎞ ⎛ 0,875 ⎞ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ = ⎜ 0,5 ⎟ + ⎜ 0 ⎟ = ⎜ 0,5 ⎟ ⎜ 0,5 ⎟ ⎜ −0,125 ⎟ ⎜ 0,375 ⎟ ⎝ ⎠ ⎝ ⎠ ⎝ ⎠ r Далее вычисляем второе приближение x (2) . Имеем ⎛ 0,8752 + 0,52 + 0,3752 − 1 ⎞ ⎛ 0,15625 ⎞ ⎜ ⎟ ⎜ r ⎟ F(x (1) ) = ⎜ 2 ⋅ 0,8752 + 0,52 − 4 ⋅ 0,375 ⎟ = ⎜ 0, 28125 ⎟ ⎜ 3 ⋅ 0,8752 − 4 ⋅ 0,52 + 0,3752 ⎟ ⎜ 0, 4375 ⎟ ⎠ ⎝ ⎠ ⎝ ⎛ 2x 2 y 2z ⎞ r ⎜ ⎟ F′(x) = ⎜ 4 x 2 y −4 ⎟ ⎜ 6 x −4 2 z ⎟ ⎝ ⎠ ⎛ 2 ⋅ 0,875 2 ⋅ 0,5 2 ⋅ 0,375 ⎞ ⎛ 1, 75 1 0, 75 ⎞ r (1) ⎜ ⎟ ⎜ ⎟ F′(x ) = ⎜ 4 ⋅ 0,875 2 ⋅ 0,5 −4 ⎟ = ⎜ 3,5 1 −4 ⎟ ⎜ 6 ⋅ 0,875 2 ⋅ 0,375 ⎟⎠ ⎜⎝ 5, 25 −4 0, 75 ⎟⎠ −4 ⎝ 1, 75 1 0, 75 1, 75 1 0, 75 r (1) det F′(x ) = 3,5 1 −4 = 1, 75 0 −4, 75 = −64, 75 5, 25 −4 0, 75 12, 25 0 3, 75 Находим обратную матрицу ⎛ −15, 25 −3, 75 −4, 75 ⎞ 1 ⎜ r (1) −1 ⎟ ⎡⎣ F′(x ) ⎤⎦ = − −23, 625 −2, 625 9, 625 ⎟ ⎜ 64, 75 ⎜ ⎟ ⎝ −19, 25 12, 25 −1, 75 ⎠ Из формулы (5) из лекции, получим второе приближение ⎛ 0,875 ⎞ ⎛ −15, 25 −3, 75 −4, 75 ⎞ ⎛ 0,15625 ⎞ 1 ⎜ r (2) r (1) r (1) −1 r (1) ⎜ ⎟ ⎟⎜ ⎟ −23, 625 −2, 625 9, 625 ⎟ ⎜ 0, 28125 ⎟ = x = x − ⎡⎣ F′(x ) ⎤⎦ F(x ) = ⎜ 0,5 ⎟ + ⎜ ⎜ 0,375 ⎟ 64, 75 ⎜ −19, 25 12, 25 −1, 75 ⎟ ⎜ 0, 4375 ⎟ ⎝ ⎠ ⎝ ⎠⎝ ⎠ ⎛ 0, 78981 ⎞ ⎜ ⎟ = ⎜ 0, 49662 ⎟ ⎜ 0,36993 ⎟ ⎝ ⎠

Аналогично находятся дальнейшие приближения ⎛ 0, 78521 ⎞ ⎛ 0, 00001 ⎞ r (3) ⎜ r (3) ⎜ ⎟ ⎟ x = ⎜ 0, 49662 ⎟ , F ( x ) = ⎜ 0, 00004 ⎟ ⎜ 0,36992 ⎟ ⎜ 0, 00005 ⎟ ⎝ ⎠ ⎝ ⎠ Ограничиваясь третьим приближением получим Ответ: x = 0, 7852, y = 0, 4966, z = 0,3699

69

Упражнение Методом Ньютона приближенно найти вещественные корни системы: Исходя из начального приближения x (0) = 1, 2 y (0) = 1, 7 2 x3 − y 2 − 1 = 0 xy 3 − y − 4 = 0 Решение: 3 2 r ⎛ 2 x − y − 1⎞ F(x) = ⎜⎜ 3 ⎟⎟ ⎝ xy − y − 4 ⎠ 3 2 r (0) ⎛ 2 ⋅1, 2 − 1, 7 − 1 ⎞ ⎛ −0, 434 ⎞ = F(x ) ⎜⎜ ⎟⎟ = ⎜ ⎟ 3 ⋅ − − 1, 2 1, 7 1, 7 4 ⎝ ⎠ ⎝ 0,1956 ⎠ ∂ f1 ∂ f1 ∂x ∂y −2 y 6x2 r = 3 F′(x) = ∂ f2 ∂ f2 3 xy 2 − 1 y ∂x ∂y

F′(1, 2;1, 7) =

6 ⋅1, 22 1, 7

3

−2 ⋅1, 7 3 ⋅1, 2 ⋅1, 7 − 1 2

=

8, 64 −3, 4 4,91

9, 4

= 97,91

−1 ⎛ 1, 2 ⎞ 1 ⎛ 9, 4 −4,91⎞ ⎛ −0, 434 ⎞ r r r r x (1) = x (0) − ⎡⎣ F′(x (0) ) ⎤⎦ F(x (0) ) = ⎜ ⎟ − ⎜ ⎟⎜ ⎟= ⎝ 1, 7 ⎠ 97,91 ⎝ 3, 4 8, 64 ⎠ ⎝ 0,1956 ⎠ ⎛ 1, 2349 ⎞ =⎜ ⎟ ⎝ 1, 6610 ⎠ Продолжая этот процесс получим x (2) = 1, 2343, y (2) = 1, 6615

70