РЕШЕНИЕ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ И ПРОБЛЕМЫ СОБСТВЕННЫХ ЗНАЧЕНИЙ
создание документов онлайн
Документы и бланки онлайн

Обследовать

Администрация
Механический Электроника
биологии
география
дом в саду
история
литература
маркетинг
математике Физика информатики химия
медицина
музыка
образование
психология
разное
художественная культура
экономика


РЕШЕНИЕ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ И ПРОБЛЕМЫ СОБСТВЕННЫХ ЗНАЧЕНИЙ

математике


Отправить его в другом документе Tab для Yahoo книги - конечно, эссе, очерк Hits: 1508


дтхзйе дплхнеофщ

Теории Юнга и Лапласа
Найти неопределенный интеграл
АНАЛИТИЧЕКАЯ ГЕОМЕТРИЯ НА ПЛОСКОСТИ
БИЛИНЕЙНЫЕ И КВАДРАТИЧНЫЕ ФОРМЫ
Тело и его свойства
Итерационные методы решения линейных уравнений
Векторное и смешанное произведение векторов, их основные свойства и геометрический смысл. Координатное выражение векторного и смешанного произведения. Условия коллинеарности и компланарности векторов.
ДИАГОНАЛИЗИРУЕМЫЕ ЛИНЕЙНЫЕ ОПЕРАТОРЫ
Решение канонической задачи линейного программирования методом перебора
ПРОЕЦИРОВАНИЕ ТОЧКИ
 

Решение систем линейных алгебраических уравнений и проблемы собственных значений

1. Нормы векторов и матриц и их свойства

В вычислительной линейной алгебре выделяют четыре основные задачи:

1) решение систем линейных алгебраических уравнений;

2) вычисление определителей;

3) нахождение обратных матриц;

4) определение собственных значений и собственных векторов.

Рассмотрим подробнее первую задачу. Пусть дана система линейных уравнений

                                                    (1.1)

В матричной форме записи эта система принимает вид

,                                                                      (1.2)

где                        

Если матрица  не является вырожденной, то решение системы существует, единственно и устойчиво ко входным данным.

Пусть - приближенное решение системы (1.1). Тогда - погрешность решения. Кроме нее качество полученного решения часто можно оценить по невязке              ,                                                                                (1.3)



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

                                                             (1.4)

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

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

1)  если 

2)

3)  - неравенство треугольника.

Существует множество различных способов введения норм. В вычислительных методах наиболее употребительными являются три нормы:

                                                                 (1.5)

                                                              (1.6)

                                                                (1.7)

При этом  Норма (1.6) является естественным обобщением на случай - мерного пространства понятия длины вектора в двух и трехмерных геометрических пространствах. Поэтому ее называют евклидовой нормой.

Абсолютной и относительной погрешностью вектора  называются выражения

                                                (1.8)

Выбор той или иной конкретной нормы в практических задачах диктуется тем, какие требования предъявляются к точности решения. Выбор нормы (1.5) отвечает случаю, когда малой должна быть суммарная абсолютная ошибка в компонентах решения; выбор (1.6) соответствует критерию малости среднеквадратической ошибки, а выбор (1.7) означает, что малой должна быть максимальная из абсолютных ошибок в компонентах решения.

Величина  называется нормой матрицы , подчиненной норме вектора , введенной в . Норма матрицы обладает следующими свойствами:

1)

2)

3)

4)

5)

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

                                                             (1.9)

                                                      (1.10)

где  - собственные числа матрицы ,

                                                              (1.11)

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

                                                        (1.12)

где  - евклидова норма матрицы

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

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

Рассмотрим систему . Пусть  задана совершенно точно, а вектор-столбец
 - приближенно.

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

                                                                 (2.1)

где

Действительно,         Тогда 

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

Вычислим максимальное значение  Тогда  Полученная величина называется стандартным  числом обусловленности и обозначается

                                                      (2.2)

Поскольку то

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

                                               (2.3)

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

                                                    (2.4)

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

3. Метод Гаусса (схема единственного деления)

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

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

                                          (3.1)

2-й шаг. Целью этого шага является исключение неизвестного  из уравнений с номерами  Пусть  - ведущий элемент второго шага; положим опять  и вычтем из третьего, четвертого,..., -го уравнений второе уравнение, умноженное на  соответственно. Получим

                                          (3.2)

где  В результате после -го шага исключения получим следующую треугольную систему уравнений:

                                       (3.3)

На этом вычисления прямого хода заканчиваются.

Обратный ход посвящен нахождению неизвестных  Из последнего уравнения системы (3.3) находим сразу  Подставляя найденное значение  в предпоследнее уравнение, получим  Осуществляя обратную подстановку, далее последовательно находим  

Общее число арифметических операций прямого хода в методе Гаусса примерно , обратного - всего около , что при большом  пренебрежимо мало по сравнению с числом операций прямого хода.

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

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

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

В качестве примера рассмотрим следующую систему:

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

Среди коэффициентов при неизвестных во втором, третьем и четвертом уравнениях максимальным по модулю является коэффициент  Переставим четвертое уравнение на место второго и исключим :

В третьем и четвертом уравнениях наибольший коэффициент  Поэтому переставим четвертое уравнение на место третьего и исключим  Тогда получим следующую систему:

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

Итак, с точностью    

4. Метод прогонки

Метод прогонки, так же как и метод Гаусса, разделяется на два этапа: прямой и обратный ход. В результате выполнения прямого хода вычисляются вспомогательные переменные - так называемые прогоночные коэффициенты. Обратный ход дает значения неизвестных.

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

                                     (4.1)

Системы такого вида часто возникают при решении различных задач математической физики и интерполяции сплайнами.

Выведем формулы метода. Из первого уравнения  найдем :

                                           (4.2)

Подставим полученное выражение для  во второе уравнение системы (4.1):

                                       (4.3)

Последнее уравнение для  подставим в третье уравнение системы (4.1) и так далее.

На -м шаге процесса  -е уравнение системы преобразуется к такому же виду:

                                               (4.4)

На последнем -м шаге подстановка в последнее уравнение системы  даст  Отсюда

                                                             (4.5)

Значения остальных неизвестных вычисляются в процессе обратного хода по формулам (4.4). Итак, прямой ход метода прогонки состоит в вычислении прогоночных коэффициентов

                        (4.6)

Обратный ход метода прогонки дает значения неизвестных по формулам

                                      (4.7)

Несложный подсчет показывает, что для реализации вычислений по описанному алгоритму требуется примерно  арифметических операций, что гораздо меньше числа операций в методе Гаусса  Кроме того структура матрицы коэффициентов системы  (4.1) позволяет использовать для ее хранения лишь  машинных слова.

Теоретические исследования показали, что для существования решения системы (4.1) и его единственности необходимо выполнение следующих условий.

Теорема 3. Пусть коэффициенты системы (4.1) удовлетворяют условиям диагонального преобладания:  тогда   и   для всех

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

В качестве примера решим следующую систему, уже встречавшуюся нам при рассмотрении кубических сплайнов:

Прямой ход.  

Обратный ход.

 Метод простых итераций

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

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

Пусть дана система - квадратная невырожденная матрица. Преобразуем ее к виду                                                                                                                  (1)

где - квадратная матрица такой же размерности что и , - вектор -столбец. В развернутой форме записи система (1) имеет вид

                                                  (2)

Операция приведения системы  к виду (2) не является очевидной и простой и требует специальных знаний, а также существенного использования специфики системы. Самый простой способ приведения системы  к виду (2) состоит в последовательном исключении из первого уравнения системы  переменной , из второго уравне-
ния - переменной  и так далее. Метод итерации в такой реализации называется методом Якоби*. Система уравнений метода Якоби имеет вид

                                 (3)

На главной диагонали матрицы  системы (3) стоят нули, а остальные элементы, очевидно, выражаются по формулам  

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

                                                        (4)

В развернутой форме записи система (4) выглядит таким образом:

                                            (5)

6. Сходимость метода простых итераций

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

                                                 (6.1)

Доказательство

Пусть в (5)  тогда  Если - точное решение системы, то оно удовлетворяет уравнению (1), то есть . Вычтем два
последних уравнения друг из друга. Получим  Найдем
норму этого выражения:  , так как неравенство верно для всех индексов от 0 до .

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

Теорема  (Апостериорная оценка погрешности решения).

Если , то справедлива следующая оценка:

                                               (6.2)

Доказательство

В предыдущей теореме имели равенство  Преобразуем
его алгебраически: .
Тогда  Отсюда легко получаем  

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

7. Метод Зейделя*

Пусть система  методом Якоби приведена к виду (3):

Метод Зейделя является лишь модификацией метода Якоби. Его основная идея состоит в том, что при вычислении очередного -го приближения к неизвестному  при  используют уже найденные -е приближения к неизвестным , а не -е приближение, как в методе Якоби. Система (3) на -й итерации будет выглядеть так:

                                   (7.1)

Введем нижнюю и верхнюю треугольные матрицы

                      и      

Тогда расчетная формула метода Зейделя примет такой вид

                                                       (7.2)

8. Сходимость метода Зейделя

Теорема 6. Пусть выполнено условие  Тогда при любом выборе  метод Зейделя сходится и верна оценка погрешности

.                                  (8.1)

Это опять априорная оценка. Ее практическое использование затруднительно. Теорема 6 сформулирована для матриц  и , однако для метода Зейделя справедлива теорема, аналогичная теореме 4, использующая только норму матрицы . Апостериорная оценка погрешности метода Зейделя дается следующей теоремой.

Теорема 7. Если , то для метода Зейделя справедлива следующая апостериорная оценка погрешности:

                                          (8.2)

Существует устойчивое заблуждение, что метод Зейделя сходится всегда быстрее, чем метод простых итераций. Это действительно так только в случае, когда матрица  симметрична и положительно определена. Однако в общем случае возможны ситуации, когда метод Якоби сходится, а метод Зейделя или сходится медленнее, или вообще расходится. Возможны и противоположные ситуации. Дело в том, что эти методы ориентированы на решение разных классов задач: метод Якоби - на системы с матрицами, близкими к диагональным, а метод Зейделя - на системы с матрицами, близкими к нижним треугольным.

Пример. Решить систему линейных алгебраических уравнений методом простых итераций и методом Зейделя с :

                      

Дана система , преобразуем ее к виду :

                               

Вычислим норму (1.11) для матриц  Имеем

               

Отсюда  Аналогично ,  Оба метода должны сходиться очень быстро. Пусть . Тогда по методу Якоби  Далее

        ,

        ,

        ,

        .

Дальнейшие итерации проводятся аналогично:

        ,

        ,

        ,

        .

Последняя итерация дает

        ,

        ,

        ,

        .

Поскольку  то  и  Таким образом, достигнута точность  за четыре итерации.

Вычисления по методу Зейделя для этого примера мало отличаются от выше приведенных. Действительно,

         то есть то же выражение, что и в предыдущем случае.

        ,

        ,

        .

Третья итерация, оказавшаяся последней, дает

        ,

        ,

        ,

        .

Достигнут тот же результат за три итерации.

9. Лабораторная работа № 9. Решение систем линейных алгебраических уравнений методом простых итераций

Метод простых итераций используется для решения разреженных систем большой размерности (~), причем матрица такой системы помимо разреженности должна быть близкой к диагональной. Метод сходится тем быстрее, чем меньше норма матрицы коэффициентов , при этом для сходимости метода необходимо  Основная формула метода

                                                     (9.1)

Если система линейных уравнений задана в традиционной форме , ее сначала нужно привести к форме (9.1) методом Якоби.

Рассмотрим пример решения такой системы в пакете Mathcad:

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

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


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

Для проверки решим эту же систему  встроенной программой lsolve, которую мы уже использовали в лабораторной работе № 4.

В заключение приведем две подпрограммы, реализующие приведение исходной системы линейных уравнений  к нужной форме и итерационные вычисления по методу Якоби:


Задание № 1. Методом простых итераций с точностью  решить систему линейных алгебраических уравнений, заданную в форме :

 

№ вари-

анта

Матрица 

Вектор

правой

части

1

1.70

0.03

0.04

0.05

0.6810

0.00

0.80

0.01

0.02

0.4803

-0.03

-0.02

-0.10

0.00

-0.0802

-0.05

-0.04

-0.03

-1.00

-1.0007

2

3.00

0.38

0.49

0.59

1.5136

0.11

2.10

0.32

0.43

1.4782

-0.05

0.05

1.20

0.26

1.0830

-0.22

-0.11

-0.01

0.30

0.3280

№ вари-

анта

Матрица 

Вектор

правой

части

3

0.77

0.04

-0.21

0.18

1.2400

-0.45

1.23

-0.06

0.00

-0.8800

-0.26

-0.34

1.11

0.00

-0.6200

-0.05

0.26

-0.34

1.12

-1.1700

4

0.79

-0.12

0.34

0.16

-0.6400

-0.34

1.08

-0.17

0.18

1.4200

-0.16

-0.34

0.85

0.31

-0.4200

-0.12

0.26

0.08

0.75

0.8300

5

0.99

-0.02

0.62

-0.08

-1.3000

-0.03

0.72

-0.33

0.07

1.1000

-0.09

-0.13

0.58

-0.28

-1.7000

-0.19

0.23

-0.08

0.63

1.5000

6

3.68

0.16

0.18

0.22

1.1604

0.12

3.59

0.18

0.21

1.2025

0.11

0.14

3.50

0.21

1.2409

0.11

0.14

0.17

3.11

1.2757

7

3.55

0.15

0.18

0.21

1.0834

0.11

3.46

0.16

0.19

1.1239

0.12

0.14

3.37

0.20

1.1607

0.10

0.13

0.17

3.28

1.1938

8

2.38

0.10

0.12

0.14

0897

0.08

2.29

0.11

0.14

3487

0.07

0.09

2.20

0.15

5712

0.06

0.08

0.11

1.10

7570

9

1.00

-0.17

0.33

-0.18

-1.2000

0.00

0.82

-0.43

0.08

0.3300

-0.22

-0.18

0.79

-0.07

0.4800

-0.08

-0.07

-0.21

0.96

-1.2000

10

0.68

0.18

-0.02

-0.21

1.8300

-0.16

0.88

0.14

-0.27

-0.6500

-0.37

-0.27

1.02

0.24

2.2300

-0.12

-0.21

0.18

0.75

-1.1300

11

0.58

0.32

-0.03

0.00

0.4400

-0.11

1.26

0.36

0.00

1.4200

-0.12

-0.08

1.14

0.24

-0.8300

-0.15

0.35

0.18

1.00

-1.4200

12

0.82

0.34

0.12

-0.15

-1.3300

-0.11

0.77

0.15

-0.32

0.8400

-0.05

0.12

0.86

0.18

-1.1600

-0.12

-0.08

-0.06

1.00

0.5700

13

0.87

-0.23

0.44

0.05

2.3000

-0.24

1.00

0.31

-0.15

-0.1800

-0.06

-0.15

1.00

0.23

1.4400

-0.72

0.08

0.05

1.00

2.4200

14

0.85

-0.05

0.08

-0.14

-0.4800

-0.32

1.13

0.12

-0.11

1.2400

-0.17

-0.06

1.08

-0.12

1.1500

-0.21

 0.16

-0.36

1.00

-0.8800

№ вари-

анта

Матрица 

Вектор

правой

части

15

0.97

0.05

-0.22

0.33

0.4300

-0.22

0.45

0.08

-0.07

-1.8000

-0.33

-0.13

1.08

0.05

-0.8000

-0.08

-0.17

-0.29

0.67

1.7000

16

4.30

0.22

0.27

0.32

2.6632

0.10

3.40

0.21

0.26

2.7779

0.04

0.09

2.50

0.20

2.5330

-0.03

0.03

0.08

1.60

1.9285

17

60



0.27

0.33

0.39

4.0316

0.15

4.70

0.27

0.33

4.3135

0.09

0.15

3.80

0.27

4.2353

0.03

0.09

0.15

2.90

3.7969

18

6.90

0.32

0.39

0.46

6632

0.19

6.00

0.33

0.41

6.1119

0.13

0.21

10

0.35

6.2000

0.08

0.15

0.22

4.20

9275

19

8.20

0.37

0.45

0.53

7.5591

0.23

7.30

0.39

0.48

8.1741

0.18

0.26

6.40

0.42

8.4281

0.12

0.21

0.29

50

8.3210

20

9.50

0.42

0.51

0.60

9.7191

0.28

8.60

0.46

0.55

10.5000

0.22

0.32

7.70

0.50

10.9195

0.17

0.26

0.35

6.80

10.9775

21

0.87

-0.22

0.33

-0.07

0.1100

0.00

0.55

0.23

-0.07

-0.3300

-0.11

0.00

1.08

-0.18

0.8500

-0.08

-0.09

-0.33

0.79

-1.7000

22

0.68

0.16

0.08

-0.15

2.4200

-0.16

1.23

-0.11

0.21

1.4300

-0.05

0.08

1.00

-0.34

-0.1600

-0.12

-0.14

0.18

0.94

1.6200

23

1.00

-0.08

0.23

-0.32

1.3400

-0.16

1.23

-0.18

-0.16

-2.3300

-0.15

-0.12

0.68

0.18

0.3400

-0.25

-0.21

0.16

0.97

0.6300

24

10.80

0.05

0.06

0.07

12.1430

0.03

9.90

0.05

0.06

13.0897

0.04

0.04

9.00

0.08

13.6744

0.02

0.03

0.04

8.10

13.8972

25

12.10

28

0.64

0.75

14.8310

0.37

11.20

86

0.69

19430

0.31

0.42

10.30

6.44

16.6926

2.60

0.37

4.81

19.40

17.0800

26

13.40

81

0.70

0.82

17.7828

0.41

12.50

6.50

0.77

19.0599

0.36

0.48

11.60

7.18

19.9744

0.31

0.43

0.54

10.70

20.5261

№ вари-

анта

Матрица 

Вектор

правой

части

27

0.94

-0.18

-0.33

-0.16

2.4300

-0.32

1.00

-0.23

0.05

-1.1200

-0.16

0.08

1.00

0.12

0.4300

-0.09

-0.22

0.13

1.00

0.8300

28

1.00

-0.34

-0.23

0.06

1.4200

-0.11

1.23

0.18

-0.36

-0.6600

-0.23

0.12

0.84

0.35

1.0800

-0.12

-0.12

0.47

0.82

1.7200

29

0.68

0.23

-0.11

0.06

0.6700

-0.18

0.88

0.33

0.00

-0.8800

-0.12

-0.32

1.05

-0.07

0.1800

-0.05

0.11

-0.09

1.12

1.4400

30

0.77

0.14

-0.06

0.12

1.2100

-0.12

1.00

-0.32

0.18

-0.7200

-0.08

0.12

0.77

-0.32

-0.5800

-0.25

-0.22

-0.14

1.00

1.5600

10. Постановка задачи нахождения собственных чисел

Вычисление собственных чисел и векторов матриц - одна из весьма сложных вычислительных задач. Рассмотрим несколько методов их нахождения.

Число  называется собственным значением (собственным числом) матрицы , если существует ненулевой вектор , удовлетворяющий уравнению

                                                                    (10.1)

 называется собственным вектором матрицы , соответствующим собственному числу .

Перепишем (10.1) в виде  Это однородная система уравнений. Чтобы существовало решение этой системы , необходимо чтобы определитель матрицы этой системы был равен нулю, то есть

                                                            (10.2)

Раскрытие этого уравнения приводит к характеристическому уравнению

                                          (10.3)

представляющему собой алгебраическое уравнение степени . Решение уравнения (10.3) дает все  собственных значений  квадратной матрицы . Если матрица  симметрическая, то все ее собственные значения - вещественные числа.

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

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

11. Подобные матрицы

Матрицы  и  называются подобными, если . При этом должна существовать невырожденная матрица подобия .

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

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

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

Теорема 8. Любую квадратную матрицу  с помощью преобразования подобия можно привести к следующему виду:

                                 (11.1)

Здесь  - собственные числа матрицы . Если , то , если же , то . Матрица (11.1) называется жордановой* формой матрицы .

12. Локализация собственных значений

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

Теорема 9. Все собственные значения матрицы  лежат в объединении кругов  Если какой-либо круг Гершгорина изолирован, то он содержит ровно одно собственное значение матрицы .

Действительно, запишем уравнение  в скалярной форме:  где  - максимальная по модулю координата вектора .

 Так как  то  то есть  

Пример. Найти все собственные числа матрицы  и изобразить на плоскости круги Гершгорина:  Вычислим сначала радиусы кругов.    Итак,    Очевидно,  и объединением всех кругов является . Все собственные числа лежат внутри круга . Найдем , решив характеристическое уравнение для данной матрицы :

 Для решения кубического уравнения применим формулы Кардано.* Уравнение вида  заменой перемен-
ной  приводится к виду , где

 В нашем случае  Число действительных решений уравнения  зависит от знака дискриминанта .  Если , то уравнение имеет три действительных различных корня, которые находятся следующим образом. Вычисляются   Далее находятся сами корни:       Итак,    с точностью  

При вычислении собственных чисел и собственных векторов симметрических матриц важную роль играет функция 

                                                               (12.1)

которая называется отношением Релея.**

Теорема 10. Пусть  - симметрическая матрица. Тогда

1) минимальное и максимальное собственное число матрицы  равны

  ;                                                (12.2)

2) вектор  является стационарной точкой , то есть  

тогда и только тогда, когда  - собственный вектор матрицы .

13. Степенной метод

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

                                                            (13.1)

Правая часть формулы для  в (13.1) - это отношение Релея при  Так как  то 

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

                                         (13.2)

При практических вычислениях вектор  нормируют, чтобы не было переполнения или исчезновений порядка. Формулы (13.1) тогда приобретают вид

                                                         (13.3)

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

Теорема 12. Пусть  - произвольное число, а  - произвольный ненулевой вектор. Тогда для любой симметрической матрицы  существует собственное число  такое, что справедлива оценка

                                                       (13.4)

В частности для степенного метода, если  - приближенно вычисленный собственный вектор, а - приближенное значение собственного числа, то

                                                (13.5)

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

Вычисления будем производить по формулам (13.3):  

 Результаты вычислений шестнадцати итераций приведены в следующей таблице:

Номер

итера-

ции 

0

-

1.0000000

0.000000

0.000000

1

1

0.107833

0.970945

0.215666

2

2.401193

0.670351

0.707602

-0.223450

3

560346

0.282393

0.954482

0.096011

4

4.128699

0.524958

0.846417

-0.089436

5

375470

0.320293

0.811308

-0.051321

6

4.703964

0.461342

0.886644

-0.032067

7

425668

0.404845

0.914362

0.006624

8

085983

0.439969

0.897778

-0.020557

9

298928

0.417814

0.908526

-0.002034

10

171134

0.431704

0.901906

-0.014094

11

251758

0.422957

0.906120

-0.007328

12

226316

0.426272

0.904522

-0.011520

13

216012

0.426340

0.904508

-0.009965

14

220049

0.426316

0.904519

-0.009929

15

219940

0.426331

0.904513

-0.009940

16

220039

0.426322

0.904517

-0.009933

Видно, что при вычислении по формуле Кардано не достигнута даже точность , так как , а не 242, как в предыдущем примере. Главный недостаток этого мето-
да - медленная сходимость, пропорциональная .

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

14. Вычисление собственных векторов методом обратных итераций

Если найдено достаточно точное приближение  к собственному числу , то, казалось бы, можно вычислить  из уравнения по определению

                                                            (14.1)

Однако из-за приближенности  матрица  будет плохо обусловленной, но невырожденной и, следовательно,  Таким образом, уравнение (14.1) мало подходит для определения .

В методе обратных итераций приближения к собственному вектору определяются как последовательные решения системы уравнений

                                                         (14.2)

причем в качестве  берут любой ненулевой вектор, например,  

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

то есть  Отсюда  Если  достаточно близко к , то  для всех  и второе слагаемое в скобке, то есть , будет мало. Тогда  то есть векторы  и  будут почти коллинеарными. Тогда вектор  будет сходиться к  по направлению со скоростью геометрической прогрессии со знаменателем  Чаще всего  и метод сходится очень быстро.

Практически метод обратных итераций используют вместе с отношением Релея:

                                            (14.3)

Пример. Найдем  для матрицы из предыдущего примера, положив  и приняв

Запишем систему из (14.3) при :  Решим ее

методом Гаусса с выбором главного элемента:

                           

                           

Отсюда  Наконец, нормируя вектор , получим

1 Лабораторная работа № 10. Вычисление собственных значений (чисел) и векторов матриц

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

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

В среде Mathcad собственные значения и векторы находятся функциями eigenvals, eigenvec, eigenvecs, genvals и genvecs. Рассмотрим их все по порядку.

Встроенная функция eigenvals(A) вычисляет вектор собственных значений матрицы , функция genvals – вектор обобщенных собственных значений  матрицы , удовлетворяющий условию

,                                                                      (11)

где - матрица с действительными элементами. Если задать , то результаты работы этих двух подпрограмм будут одинаковыми.

Введем с клавиатуры начало программы

    

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

Эти вектора удовлетворяют основному определению  (см. ниже). Функции eigenvecs и genvecs также дают все нормированные собственные векторы заданной матрицы. Координаты собственных векторов расположены по столбцам результирующей матрицы, порядок расположения собственных векторов соответствует порядку собственных чисел, возвращаемых функциями eigenvals и genvals. Однако в данном случае собственные векторы относятся к иному базису линейного пространства и имеют другие координаты.

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

Поскольку функции, реализующей формулы (13.1) степенного метода, в пакете
Mathcad нет, составим такую подпрограмму сами. В качестве исходных данных будем рассматривать саму матрицу  и произвольный вектор , необходимый для запуска процесса итераций по формулам (13.1). Сама подпрограмма весьма проста и имеет следующий вид:

Найдем два первых максимальных по модулю собственных числа матрицы


Вычисление собственного вектора можно встроить в подпрограмму  по формулам (14.2) или (14.3). Запрограммируем, однако, его нахождение отдельно:


Задание № 1. Определить собственные значения и собственные вектора матрицы  средствами пакета Mathcad, затем найти максимальное по модулю собственное число и соответствующий ему собственный вектор с помощью подпрограмм

1.                    2.

3.                    4.

                    6.

7.                    8.

9.                     10.

11.                   12.

13.                 14.

1                 16.

17.                 18.

19.           20.

21.                 22.

23.                 24.

2                  26.

27.                 28.

29.                 30.



* Карл Густав Якоб Якоби  (1804-1851 ) - немецкий математик.

* Людвиг Зейдель  (1821-1896) - немецкий астроном и математик.

* Мари Энмон Камиль Жордан (1838-1922) - французский математик.

** Семен Аронович Гершгорин (1901 - 1933) - российский математик.

* Джироламо Кардано (1501-1576) - итальянский математик.

** Джон Уильям Рэлей  (1842 -1919) - английский физик и математик.