Учебник - Практические занятия по вычислительной математике - Аристова, страница 8

Эта матрица отличается отматрицы A только двумя строками и двумя столбцами (с номерами i и j).Так как евклидова норма матрицы не изменяется при ортогональных преобразованиях, то легко получить соотношение между суммами квадратоввнедиагональных элементов старой и новой матриц:21 aˆkl2   akl2  2aij2  (a jj  aii )sin 2  2aij cos 2 .2k lk lОчевидны условия минимизации суммы в левой части последнегоравенства. Следует на текущей итерации выбирать индексы так, чтобывыполнялось условиеaij  max akl , а угол поворота выбирается изk lусловия20  (a jj  aii )sin 2  2aij cos 2 .Тогда он удовлетворяет условию tg 2 2aij,  .4aii  a jjНезависимо от наличия кратных собственных значений метод вращений обладает квадратичной сходимостью.

Это означает, что для нормы46II.7. Задачи на доказательствовнедиагональных элементов матрицы Aoff A( ) a 2jk , за число1 j  k  nшагов N = n(n – 1)/2, достаточное, чтобы выбрать каждый наддиагональный элемент по одному разу, эта норма уменьшается квадратично:off(Ai+N) = O(off2(Ai)).Выбор максимального по модулю внедиагонального элемента – затратная операция, поэтому часто реализуется метод вращений с барьерами. Его идея состоит в следующем. При переборе внедиагональных значений вращение производится тогда, когда значение элемента по абсолютной величине превосходит некоторую величину (барьер). Если всеэлементы меньше барьера, его значение уменьшается, например, на порядок, и снова начинается циклический перебор внедиагональных элементов.

Подробнее о методе вращений смотри в [11].Метод обратной итерации применяется для поиска собственного числа,наиболее близкого к данному. Суть его заключается в следующем. Рассмотрим равенство Au = λu. Зафиксируем параметр a. Тогда(A – aE)u = (λ – a)u. Верно будет и равенство (A – aE) - 1 u = u/(λ - a).

Ноесли мы интересуемся собственным числом, наиболее близким к a, тосреди собственных чисел матрицы (A – aE)-1 именно 1/(λ – a) будетнаибольшим по абсолютной величине. Для его вычисления можно использовать степенной метод, но так как нам фактически необходимы степени обратной матрицы, то в степенной метод вносится модификация,теперь uk = (A – aE)uk+1. Вот она, обратная итерация – для поиска следующего приближения в степенном методе надо решать СЛАУ.

Причем чемближе находится искомый корень характеристического уравнения к выбранному параметру a, тем эта СЛАУ ближе к вырожденной со всеми вытекающими отсюда трудностями. Подробнее о методе обратной итерациисм., например, [3].II.7. Задачи на доказательствоII.7.1. Является ли выражениеmin(|x1| + 5|x2|, 5|x1| + |x2|)нормой вектора x в R2?II.7.2.

Нормы ||•||I и ||•||II называются эквивалентными, если для всехx  R n справедливы неравенства с постоянными α и β, не зависящими отвыбора x:α||x||I ≤ ||x||II ≤ β||x||I .47II. ЭЛЕМЕНТЫ ПРИКЛАДНОЙ ЛИНЕЙНОЙ АЛГЕБРЫНайти константы эквивалентности, связывающие три основные нормывекторов.II.7.3.

Доказать, что если C – симметричная положительно определеннаяматрица, то (Cx, x) можно принять за норму вектора x. Найти константы эквивалентности, связывающие эту норму с евклидовой нормой вектора.II.7.4. Доказать утверждения (2.3а), (2.3б), (2.3в).II.7.5. Показать, что модуль любого собственного значения матрицы небольше любой ее нормы.II.7.6. Показать, что для подчиненных норм матриц справедливо неравен2ство: A 3  A 1 A 2 .II.7.7. Доказать, что для вектора x = (x1,x2) и h > 0 выражение||x||h = max(|x1|, |x2 – x1|/h) является нормой. Найти матричную норму, подчиненную этой векторной норме.1/ 2 nII.7.8. Нормой Фробениуса матрицы называется N ( A)    aij2  . Пока i , j 1 зать, что эта норма согласована сама с собой, т.е. N(AB) ≤ N(A) N(B) инайти константы эквивалентности, связывающие эту норму матрицы снормами матриц, подчиненными трем основным нормам векторов.

Показать, что норма Фробениуса не является операторной нормой.II.7.9. Max нормой матрицы называется ( A)  max aij . Показать, что этаi, jнорма не является согласованной сама с собой, а выражениеM(A) = n·η(A) вводит самосогласованную норму матриц.

Для M(A) найтиконстанты эквивалентности с нормами матрицы, подчиненными трем основным нормам векторов. Показать, что норма M(A) не является операторной нормой.II.7.10. Пусть числа dk > 0, k = 1, ..., n. Доказать, что max(dk |xk|) есть нормавектора x. Найти норму матрицы, подчиненную этой векторной норме.II.7.11. Пусть числа dk > 0, k = 1, ..., n. Доказать, чтоndk 1kxkесть нормавектора x. Найти норму матрицы, подчиненную этой векторной норме.48II.7. Задачи на доказательствоII.7.12. Пусть числа dk > 0, k = 1, ..., n.

Доказать, чтоndk 1kxk2 есть нормавектора x. Найти норму матрицы, подчиненную этой векторной норме.II.7.13. Доказать, что max1 i  nixk 1есть норма вектора x. Найти норму мат-kрицы, подчиненную этой векторной норме.II.7.14. Проверить, что xp1/ p N  | xi | p  i 1, p ≥ 1 является нормой в про-странстве CN векторов с комплексными координатами. Показать, что приx  CN справедливо неравенство ||x||p ≤ c (||Re x||p + ||Im x||p), c = const.Найти такую постоянную c0, что c0 (||Re x||2 + ||Im x||2) ≤ ||x||2, для всех длявсех x  CN.II.7.15. Пусть ||•|| – некоторая норма в RN. Доказать, что равенствоx *  max  (x, y ) y  также задает норму в RN, называемую двойственy 0ной к ||•||.II.7.16.

Пусть B – невырожденная матрица, ||•|| – некоторая норма в пространстве векторов размерности N. Доказать, что ||x||* = ||Bx|| также является нормой в пространстве векторов. Какая норма в пространстве матрицпорождается нормой ||x||* в пространстве векторов?II.7.17.A1Показать, inf  Axx0x .чтоеслиA–невырожденнаяматрица,тоII.7.18.

Доказать неравенство ||A||3 ≤ ||A||1/2||AT||1/2 для любой нормы A,подчиненной какой-либо векторной норме.II.7.19. Доказать, что если A = AT, то A 3  max ( Ax, x) xy 023.II.7.20. Пусть ||•|| – норма в пространстве матриц, подчиненная некоторойнорме векторов. Доказать согласованность этой матричной нормы, т.е.справедливость неравенства ||AB|| ≤ ||A|| ||B||.II.7.21. Пусть A = AT > 0 и ||x||A = (Ax, x)1/2. Доказать, что для произвольного многочлена pm(t) степени m ≥ 0 верно равенство ||pm(A)||A = ||pm(A)||3.49II. ЭЛЕМЕНТЫ ПРИКЛАДНОЙ ЛИНЕЙНОЙ АЛГЕБРЫII.7.22. Привести пример положительно определенной матрицы, спектркоторой не является вещественным.II.7.23.

Пусть A = AT > 0 и F(x) = 0.5·(Ax,x) – (b,x) – квадратичная функция. Доказать, что:1) F (x)  1/ 2 x  x*2A2 1/ 2 x* , где x* – точное решение системыAx = b;2) равенство F (x* )  minn F (x) выполнено тогда и только тогда, когдаxRx* – точное решение системы Ax = b;3) для градиента функции F(x) справедлива формула F (x)  Ax  b .II.7.23. Доказать, что max норма матрицы M ( A)  n max aij1 i , j  nи норма1/ 2 nФробениуса N ( A)    aij2  i , j 1 не подчинены никаким векторным нормам.II.7.24. Можно ли утверждать, что если определитель матрицы мал, томатрица плохо обусловлена?II.7.25.

Доказать: µ(A·B) ≤ µ(A)·µ(B) для любой из норм матриц, согласованных с нормами векторов, и любых квадратных матриц(A, B – квадратные матрицы). Численно показать справедливость этогонеравенства для матриц вида1 23 1A.; B  1 32 1II.7.26. Показать, что если A – нормальная матрица (AT·A = A·AT), то:||A|| = R(A), где R(A) – спектральный радиус матрицы. Вычислить спектральный радиус и число обусловленности матрицы10  1A  1001001.II.7.27. Доказать, что при условии наличия диагонального преобладания уматрицы системы метод Зейделя сходится, причем быстрее метода Гаусса–Якоби.II.7.28. Записать методы Гаусса–Якоби и Зейделя в каноническом виде.II.7.29.

Используя введение метода верхней релаксации покомпонентнокак50II.7. Задачи на доказательство(k 1)(k )(k 1)(k ) ω z i u i  ,где zi(k) – i-я компонента решения, полученная методом Зейделя, получитьматричное представление метода верхней релаксцииui ui(Lu(k 1)  Du(k 1) )  (  1)Du(k )  Uu(k )  f .II.7.30. Для СЛАУ при заданном f = (f1, f2) найти наименьшее число ν(f),при котором независимо от ∆f выполнено: ||δu|| ≤ ν(f)||δf||. Для даннойСЛАУ найти тот вектор f, которому соответствует наименьшее число ν(f),а также само значение ν(f) для трех норм векторов: ||•||1, ||•||2, ||•||3.u  3u2 f1u  u  f1u  0.99u2  f1.

б)  1 2а)  1. в)  1.uuf 1 20.99u1  u2  f 22  3u1  u2  f 2II.7.31. Для системы линейных алгебраических уравнений Ax = f,A = A*> 0 найти такую правую часть f, чтобы при фиксированной относительной ошибке задания правой части δ = ||δf|| / ||f|| относительная погрешность решения была бы минимальна и выполнялась оценка||δx|| / ||x|| ≤ ν ||δf|| / ||f||. Найти значение ν. Используется евклидова нормавекторов.II.7.32. Показать, что минимальное и максимальное значение параметраν(f), определяемого какν(f) = ||f||||A–1|| / ||u||,соответствуют векторам правых частей СЛАУ Au = f, равным собственным векторам uk, соответствующим максимальному и минимальному собственным значениям A.

Найти эти собственные значения λmax и λmin, атакже их собственные векторы umax и umin для СЛАУ вида при использовании евклидовой нормы векторов. u1  u2  f1 u  0.99u2  f1а) б)  1u1  u2  f 20.99u1  u2  f 2II.7.33. Докажите, что при любом начальном векторе (x(0), y(0), z(0))T последовательности векторов (x1(k), y1(k), z1(k))T и (x2(k), y2(k), z2(k))T, определяемыеравенствамиx( k 1)  x( k )  0.2 y1( k )  3,1y1( k 1)z1( k 1)1 0.2 x1( k )  0.1y1( k )  0.1z1( k )  2,  0.3x1( k )  0.2 z1( k )  151II. ЭЛЕМЕНТЫ ПРИКЛАДНОЙ ЛИНЕЙНОЙ АЛГЕБРЫиx ( k 1)  (2 y ( k )  30) / 9,2y2( k 1)z2( k 1)2(2 x2( k )  z2( k )  20) / 11, (3x2( k )  10) / 8сходятся, причем к одному и тому же предельному вектору (x*, y*, z*)T.

Запишите линейную систему стандартного вида, решением которой являетсяэтот предельный вектор. За сколько шагов итераций по данным формуламможно получить предельный вектор с точностью до ε = 10 –6 (в кубическойнорме), если за начальное приближение принять нулевой вектор?II.7.34. Показать, что μ(A) ≥ 1 для любой матрицы А.II.7.35.