Новости

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

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






Вычислительные алгоритмы линейной алгебры на 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. Происхождение, развитие и применение алгебры