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

Найти число обусловленности матрицы А в матричной норме,подчиненной евклидовой норме вектора, выразив его через число обусловленности матрицы В, если А = В∙В > 0.II.7.36. Пусть A = AT > 0, λA  [m, M] и A ≠ βE. Доказать, что μ(A + αE)монотонно убывает по α при α > 0.II.7.37. Найти область сходимости метода Якоби и метода Зейделя длясистем с матрицами вида:  0   0  0    0 а)      , б)  0  0  , в)    0  , г)      . 0   0   0  0 0 II.7.38. Показать, что число обусловленности СЛАУ с симметричной матmax  kAрицей Au = f равно   k.min  kAkII.7.39.

Доказать, что для систем линейных уравнений второго порядка(n = 2) методы Якоби и Гаусса–Зейделя сходятся и расходятся одновременно.II.7.40. Показать, что существует система уравнений третьего порядка,для которой метод Якоби сходится, а метод Гаусса–Зейделя расходится.II.7.41. Показать, что существует система уравнений третьего порядка,для которой метод Гаусса–Зейделя сходится, а метод Якоби расходится.52II.8. Задачи с решениямиII.8.

Задачи с решениями 18 6 7   x1   13 II.8.1. Дана система линейных уравнений  6 6 0   x2    6  .   7 0 x   6 6 3  Вычислить число обусловленности матрицы А в трех нормах.Решение. Для этого необходимо вычислить обратную матрицу и собственные значения матрицы (очевидно, что матрица самосопряженная!)Обратная матрица1 18 6 7  36 36 42  6 6 0   1  36 108 42  .138  7 0 6 4242108Число обусловленности в первой и второй нормах 31∙192/138 ≈ 43.Собственные значения (18  )(6  )2  49(6  )  36(6  )  0  6,   1,   23Число обусловленности равно 23.II.8.2.

Для системы линейных алгебраических уравненийAx = f, 2 1  3A, f    0 21построить сходящийся вариант метода простых итераций. Оценить оптимальное значение итерационного параметра. Оценить число итераций,необходимое для достижения точности 10 –3 , если начальное приближение к решению x0 = (0, 0)T.Решение. Матрица системы – несамосопряженная, не положительная.

Можно сделать ее самосопряженной положительной матрицей,умножив обе части системы на сопряженную.Тогда система перейдет в равносильную линейную систему Bx = g, 4 2  6 B, f   . 2 5 5Собственные значения матрицы B есть 9  172. Итерационныйметод есть xn+1 = (E – τB)xn + τf.

Оптимальное значение параметра 2/9. Заодну итерацию невязка убывает в 17 9 раз, для числа итераций в третьейнорме имеем уравнение53II. ЭЛЕМЕНТЫ ПРИКЛАДНОЙ ЛИНЕЙНОЙ АЛГЕБРЫ17 9N 61  103.II.8.3. Получить оценку относительной погрешности решения СЛАУ приточном задании матрицы системы и фиксированной относительной погрешности правой части в зависимости от правой части системы.Решение.

В этом случае обусловленность системы, вообще говоря, зависит и от f, и от Δf и удовлетворяет неравенству (f , f ) ufuuufЕго можно определить как точную верхнюю грань отношенияff.по Δf,что соответствует наихудшей ситуации. Тогда(f )  supfufuf supffuuffsupu fA 1fffA 1 .uОценим точную верхнюю грань и точную нижнюю грань этого выражения.fAusup A1  A1  sup A1  A  ( A),uuffс другой стороны,inf (f )  inf Aff1fu inf Af1 u sup  f  f 1 A1 sup f1A ff1 1.Параметр ν(f), характеризующий обусловленность системы, зависитот правых частей.

Более тонкая его оценка есть (f )  A 1fu, причем1  (f )  . Так как такую оценку провести не всегда возможно, то чащеиспользуется точная верхняя грань A 1 A .II.8.4. При решении СЛАУ методом Гаусса из-за погрешностей округления возникла ненулевая невязка. Предложить процедуру уточнения численного решения СЛАУ, если невязка известна.Решение. Полученное решение можно улучшить следующим образом. Пусть r1 = f – Au1 есть невязка, допущенная при решении рассматриваемой системы (u1 – полученное численное решение) за счет ошибкиокруглений.

Очевидно, что погрешность ε1 = u – u1 удовлетворяет СЛАУAε1 = r1 так как Aε1 = Au – Au1 = f – Au1.Решив последнюю систему, получаем ε1, после чего уточняем решение:54II.8. Задачи с решениямиu2 = u1 + ε1.Если после такого уточнения невязка велика, то эту процедуру можнопродолжить.II.8.5. Записать формулы метода Гаусса в виде последовательности умножения исходной матрицы на соответствующие матрицы элементарныхпреобразований.Решение. Рассмотрим метод Гаусса с позиции операций с матрицами.Пусть A1 – матрица системы после исключения первого неизвестногоa1n  a11 a12 a1311a12 n  0 a22 a2311 TА1   0a132 a133a13n  , f1  { f1, f 2 , , fn } .11  0 a1aan2n3nn Введем новую матрицу000  1100  21010 .N1   31 001 n1Очевидно A1 = N1A, f1 = N1f.

Аналогично, после второго шага система приводится к виду A2u = f2, где A2 = N2A1, f2 = N2f1, a11 a121 0 a22A1   00 000 11 0320N2  0n 2a13a1232a33an230010a1n a12 n a32n  ,2 ann0 0 0  , f2  f1 , f 21 , f32 ,1 55, f n2T.II. ЭЛЕМЕНТЫ ПРИКЛАДНОЙ ЛИНЕЙНОЙ АЛГЕБРЫПослеn–1шагаполучимAn1u  fn1, An1  Nn1  An2 ,fn1  Nn1fn2 , a11 0A n 1   0 0 1 0N n 1   0 0fn1  { f1 , f 21, f32 ,a12a13a1220a1232a33000100001n,n 1a1n a12n a32n  ,( n 1) ann0 0 ,0 1 , f nn1}T .В итоге получаются матрица и векторN2 N1f , откуда A  N11N21f (n1)  Nn1N 21   1 01N n 1   0 010001320010n 20An1  Nn1Nn11  An1 .

При этом000,1 01000000101n,n 1.После введения обозначений U  An1, L  N11N2156N2 N1A ,Nn11, гдеII.9. Теоретические задачи0 11 21L  31 32 n1 n 2получим A = LU.001n3000,1 II.9. Теоретические задачиII.9.1. Дана система линейных алгебраических уравнений Ax = b: 101 110  312 а) A  ; b;110 122  342  101 110  92 б) A  ;; b 110122 98  82 90  254 в) A  ;; b 281  90 101 101 90  112 г) A  .; b  98  90 82 Найтиτопт,прикоторомметодпростойитерацииxk+1) = (E – τA)x(k) + τb будет сходиться быстрее всего. Оценить скоростьсходимости.Пусть τ принадлежит интервалу 0< τ < τопт.

Получить оценку скорости сходимости в этом случае. Можно ли так задать вектор начальногоприближения x0, чтобы скорость сходимости в этом случае была бы выше,чем при оптимальном τопт? Если это возможно, то указать такое x0.II.9.2. Дана система линейных алгебраических уравнений Ax = b:А) Оценить максимально точно относительную погрешность ||Δx||/||x||в заданной норме.Найти вектор ошибки Δb, на котором эта оценка достигается. Прикаком Δb относительная ошибка ||Δx||/||x|| будет минимальной? Найти ее. 101 110  312  b 1а) A   0.01 ; x 1  max xi ,; b;b1i110 122  342 57II.

ЭЛЕМЕНТЫ ПРИКЛАДНОЙ ЛИНЕЙНОЙ АЛГЕБРЫ 101 110  92  b 2б) A   0.01 ; x;; b b2 98  110 122 2 101 90  112  b 2в) A   0.01 ; x;; b b2 98  90 82 2xi,ixi,i 65 72 137  b 3г) A   0.01 ; x 3  (x, x) ,; b;b3 72 82  154  50 70 120  b 3д) A   0.01 ; x 3  (x, x) ,; b ;b3 70 101 171 Б) RQI – алгоритмом, начиная его с различных векторов.II.9.3. Дана система линейных алгебраических уравнений Ax = b: 65 80 145 а) A  ; b; 80 101 181  65б) A   72 50в) A   7072 137 ; b;82  154 70  120 ; b.101 171 Найти τопт, при котором метод простой итерации xk+1 = (E – τA)xk + τb будет сходиться быстрее всего.

Оценить скорость сходимости.Пусть τ принадлежит интервалу τопт < τ < τmax. Получить оценку скорости сходимости в этом случае. Можно ли так задать вектор начальногоприближения x0, чтобы скорость сходимости в этом случае была бы выше,чем при оптимальном τопт? Если это возможно, то указать такое x0.II.9.4. Найти области сходимости методов простой итерации и Зейделя p qдля систем x = Rx + g, где R = . q pII.9.5.

Дана система 10 x  y  z  1, x  20 y  3z  2,2 x  3 y  10 z  1.58II.9. Теоретические задачиНаписать формулы для вычисления решения итерациями, используядиагональное преобладание. Сколько итераций достаточно, чтобы уменьшить погрешность исходного приближения в тысячу раз?II.9.6. Предположим, что некоторая система размерности n x n видаx = Rx + c с матрицей, имеющей норму ||R|| ≈ 0.5, решается методом простых итераций с уровнем абсолютных погрешностей арифметическихопераций порядка 10 –6. Допустим, что при этом первая итерационная поправка имеет норму ||x(1) – x(0)|| ≈ 1. Каким числом следует ограничить количество итераций, чтобы вычислительная погрешность не стала существенно превышать погрешность метода?II.9.7.

Для системы уравнений103 u1  u2  f1u1  u2  f 2ответить на следующие вопросы.а) Каково число обусловленности µ системы, если в качестве нормыпроизвольного вектора u используется ||u|| = max{|u1|, |u2|}?б) Какова допустимая относительная погрешность при заданииf = (f1, f2)T, при которой относительная погрешность решения не превосходит 10–2?в) Пусть f1 = 2, f2 = 1. С каким числом знаков надо ввести вычисления по методу Гаусса без выбора главного элемента, чтобы {u1, u2} имелихотя бы по одному верному десятичному знаку?Тот же вопрос для метода Гаусса с выбором главного элемента.II.9.8. Найти решения двух СЛАУ:44u  3vu  3v(), ()u3.00001v4.00001u2.9999v 4.00001и объяснить результат.II.9.9.

Для СЛАУ 10u1  u2 u  10u  u23 1u2  10u3  u4u98  10u99  u100uu 1 2   u99  u100 1, 2, 3,, 99, A,59II. ЭЛЕМЕНТЫ ПРИКЛАДНОЙ ЛИНЕЙНОЙ АЛГЕБРЫгде A – параметр, описать алгоритм метода Гаусса без выбора главногоэлемента при A =100. Предложить алгоритм экономичного решения данной системы уравнений, если нужно получить решение системы длянабора значений параметра A. 6 2 II.9.10.

К матрице A  4 0 примените LU–алгоритм и сравните результат третьего шага с точнонайденными собственными числами.II.9.11. Найти область значений итерационного параметра τ, при которыхитерационныйпроцессxk + 1 = (E – τA)xk + τfсходится,еслиRe{λ(A)}≥ δ > 0.II.9.12. Запишите итерационный процесс Якоби нахождения решения системы 5 x1  2 x2  x3  x4  9, x  4x 2 x4  10, 122 x1  3x2  9 x3  x4  10,3x1 x3  6 x4  5.Каким должен быть критерий окончания процесса итерирования, чтобымаксимальная из абсолютных погрешностей компонент приближенногорешения не превышала заданного малого ε?II.9.13.

Предложить способ решения системы методом простых итерацийс оптимальным параметром. Найти оптимальный параметр и количествоитераций, необходимое для достижения точности 10 –43x  z  6,а)  x  y  z  2,3 y  z  3.12 x  2 y  2,б)  11 x  3 y  z  12,2214 z  2 y  6.В качестве начального приближения берется x0 = (0, 0, 0)T .II.9.14.