Новости

Вычислительные алгоритмы линейной алгебры

Работа добавлена:






Вычислительные алгоритмы линейной алгебры на http://mirrorref.ru

Вычислительные алгоритмы линейной алгебры

(лекции для студентовIV курса ПМ).

К задачам линейной алгебры относятся задачи:

а) численного решения СЛУ;

б) обращения матриц;

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

г) нахождения собственных значений и собственных векторов.

 Формальный подход метода Крамера требует для матрицы порядкаn число операцийn!n. Приn=100 это уже практически не решаемая задача по времени и по ошибкам округления.

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

Методы решения алгебраических задач делятся на точные и итерационные.

Под точными методами понимается методы, которые дают решение задачи за конечное число арифметических операций. Пример - различные модификации метода Гаусса.

Итерационные методы дают приближенное решение СЛУ. Решения находится как предел последовательных приближений, вычисленных некоторым единообразным процессом. Важными характеристиками таких методов является их сходимость, а также быстрота сходимости.

Литература

  1. Д.К. Фадеев, В.Н. Фадеева. Вычислительные методы линейной алгебры. СПб.: Лань, 2002.
  2. Вержбицкий В.М. Численные методы (линейная алгебра и нелинейные уравнения). - М.: Издательский дом "ОНИКС 21 век", 2005. 432 с.
  3. К.Ю. Богачев. Практикум на ЭВМ. Методы решения линейных систем и нахождения собственных значений. М.: МГУ, 1999.
  4. В.В. Воеводин. Вычислительные основы линейной алгебры. М.: Наука, 1977.

ПустьV – векторное пространство.

Определение 1.Нормой вектора  называется сопоставляемое вектору неотрицательное число:

  1. при и

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

Легко видеть, что . □Действительно, ■

Пространство  становится нормированным, если норма введена по формуле

Эти нормы эквивалентны при различных

Наиболее употребительны следующие нормы:

  1. Кубическая (Чебышевская) норма

Множество :  образует куб в .

  1. Сферическая (евклидова) норма

Множество :  образуетсферу в .

  1. Октаэдрическая норма

Множествоx:  образует в  октаэдр.

Введенные нормы связаны соотношениями:

Первые два неравенства очевидны.

Левая часть последнего неравенства следует из неравенства Коши – Буняковского

.

Пусть рассматривается последовательность векторов ;

Определение 2. Если существует , то вектор  называетсяпределом последовательности .  Пишут .

Аналогично определяется сходимость последовательности матриц.

Утверждение 1.  для любой нормы, вводимой выше.

Доказательство: самостоятельно.

Рассмотрим пространство матриц размера , т.е. . Это векторное пространство размерности  и в нём можно ввести различные нормы.

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

Определение 3.Нормой квадратной матрицы  называется неотрицательное число :

1) , если  и

2).

3) .

4) .

Простейшие свойства матричной нормы:

1. , где  - единичная матрица.

□ Действительно,

2. , или в частности,

□ Действительно,

(число обусловленности матрицы A)Не любая векторная норма в пространстве матриц является матричной.

Рассмотрим  и пусть . Рассмотрим

Тогда

и .

То есть получим .

Рассмотренная норма может быть подправлена до матричной. А именно, рассмотрим

-кубическую норму.

Первые три свойства для кубической нормы выполняются. Проверим четвертое.

□  Пусть , тогда .

Фробениусова (или обобщенно-сферическая) норма:

Легко видеть, что .

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

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

Утверждение2. Кубическая норма  согласована с кубической, сферической и октаэдрической нормами вектора, а Фробениусова норма согласована со сферической нормой вектора.

□ Доказательство: самостоятельно (см.[1], стр.131). ■

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

( - заданная норма вектора)

Утверждение 3. Построенная таким образом норма удовлетворяет всем условиям определения 3 матричной нормы.

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

  1. Очевидно, что . Если , то
  2. .
  3. .
  4. здесь условие  выполняется в силу рассмотрения согласованных норм.

Определение 5. Если  является векторной нормой, то норма матрицы , определяемая формулой , называетсяподчиненной(или операторной, или индуцированной) по отношению к векторной норме .

В силу непрерывности нормы можно записать ,

или

.

(максимум достигается в силу непрерывности нормы и замкнутости множества )Свойства подчиненной нормы.

1. Подчиненная норма является наименьшей из всех согласованных норм.

и . (maxТогда  ■

2.Если  - подчиненная норма, то .

□ ■

Отсюда следует, что кубическая и Фробениусова нормы не подчинены никакой векторной норме, т.к. .

Далее найдем матричные нормы, подчиненные трем основным векторным нормам.

1.Если

- кубическая норма,

то соответствующей подчиненной матричной нормой являетсямаксимальная строчная норма, т.е.

.

Покажем, что : где  (maxПусть  достигается при  . Рассмотрим вектор :   ■

2.Если

- октаэдрическая норма,

то подчиненной матричной является норма

максимальная столбцовая норма.

Действительно,

Очевидно, что  и . ■

3.спектральная норма:

- собственные значения матрицы

Здесь -сопряженная к  матрица: .

Если рассматривается евклидово вещественное пространство, то .

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

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

□ Действительно, если- собственные значения и - соответствующий собственный вектор, то

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

Для матрицы  справедливо условие самосопряженности.

Пусть собственные значения матрицы  перенумерованы в порядке убывания.

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

Теперь докажемподчиненность спектральной нормы евклидовой (сферической) норме.

□  Для  имеем  (разложение по базису).

Выбираем . Тогда .

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

Замечание.Для матричных норм выполняются неравенства

Доказательство смотри в [1], стр. 134-136.

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

Утверждение 4. Для всякой матрицы  и всякой матричной нормы на  справедливо неравенство: .

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

Замечание 1.Если  , то . Это следует из того, что собственные значения матрицы  равны квадратам матрицы собственных значений матрицы , а , где- максимальный модуль собственных значений.

Определение 7. Матрица  называется унитарной, если                                      (1)

Если  и выполняется (1), то  называется ортогональной.

Определение 8.Унитарно инвариантной матричной нормой называется норма , удовлетворяющая равенству , где  унитарные матрицы.

Утверждение 5. Спектральная норма является унитарно инвариантной.

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

■Далее докажем несколько теорем о сходимости последовательности матриц.

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

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

Очевидно, чтоУтверждение 7.Для того, чтобы  достаточно, чтобы хоть одна из норм  была меньше единицы.

если  ■

Утверждение 8. Для того, чтобы ряд  (2)

сходился   при .

Тогда сумма ряда (2) равна .

□ Пусть . Тогда в силу утверждения 6 все собственные значения  по модулю меньше единицы. Тогда и значит  В силу тождества , умноженного справа на , получаем:  Отсюда при .■

Следствие. Если хотя бы для одной из норм , то матрица  обратима, а ряд (2) сходится.

Легко видеть, что оценки остаточных членов ряда: .

Утверждение 9. Если - обратимо, а такова, что  в некоторой норме, то - обратимо, причем .

□  Рассмотрим матрицу . Так как по условию , то по следствию  и . Тогда - обратная к . Действительно,  ■

Вычислительные алгоритмы линейной алгебры на http://mirrorref.ru


Похожие рефераты, которые будут Вам интерестны.

1. Реферат Вычислительные алгоритмы линейной алгебры

2. Реферат Использование MatLab при решении задач линейной алгебры

3. Реферат Вычислительные кластеры

4. Реферат ЦИКЛИЧЕСКИЕ ВЫЧИСЛИТЕЛЬНЫЕ ПРОЦЕССЫ

5. Реферат ЭВМ - электронно-вычислительные машины

6. Реферат Вычислительные возможности табличного процессора

7. Реферат Локальные вычислительные сети. Состав и архитектура

8. Реферат АВИАЦИОННЫЕ ПРИБОРЫ И ИЗМЕРИТЕЛЬНО-ВЫЧИСЛИТЕЛЬНЫЕ КОМПЛЕКСЫ

9. Реферат ВЫЧИСЛИТЕЛЬНЫЕ СИСТЕМЫ, СЕТИ И ТЕЛЕКОММУНИКАЦИИ ТЕСТОВЫЕ ЗАДАНИЯ

10. Реферат Элементы алгебры логики