Г.М. Кобельков - Задачи к экзамену по курсу Методы вычислений (1119785), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Построить кубический сплайн по значениям f (0), f (1).Решение. Учитывая так называемые «естественные» граничные условия (p′′ (0) = p′′ (1) = 1), имеем:P (x) = f (0) + f (1) − f (0) x.Задача 14. Построить кубический сплайн по значениям f (0), f (1), f (2).Решение. Необходимо построить два кубических сплайнаP1 = A1 x3 + B1 x2 + C1 x + D1 ,P2 = A2 x3 + B2 x2 + C2 x + D2 .На них накладываются следующие условия:P ′′ (0) = P2′′ (2) = 0 (естественные условия), 1′′P1 (1) = P2 (1) (гладкость),P ′′ (1) = P ′′ (1) (ещё большая гладкость),12P1 (0) = f (0) (совпадение в узлах),P1 (1) = P2 (1) = f (1),P2 (2) = f (2).5На неизвестные коэффициенты сплайнов получаем следующую систему:B =0 16A2 + B2 = 03A1 + 2B1 + C1 = 3A2 + 2B2 + C23A + B = 3A + B1122D1 = f (0)A1 + B1 + C1 + D1 = f (1)A2 + B2 + C2 + D2 = f (1)8A2 + 4B2 + 2C2 + D2 = f (2)Решение будет иметь такой вид:3A1 = 12 (f (0) + f (2) − 2f (1))B1 = 0C1 = f (1) − f (0) − 3 (f (0) + f (2) − 2f (1))12D = f (0)13(f (0) + f (2) − 2f (1))A2 = − 123B2 = 2 (f (0) + f (2) − 2f (1))C2 = f (1) − f (0) − 74 (f (0) + f (2) − 2f (1))D2 = f (0) − 12 (f (0) + f (2) − 2f (1))Задача 15.

Доказать, что если A = AT > 0, то aii > 0.Решение. Пусть ei — стандартные базисные векторы. Тогда aii = (Aei , ei ) > 0, по определению симметричной положительно определённой квадратичной формы. Задача 16. Пусть числа pk (k = 1, . . . , n) являются положительными. Доказать, что выражениеkxkp :=nXk=1|xk | pkопределяет норму вектора x = (x1 , . .

. , xn ). Найти норму матрицы, согласованную с этой нормой вектора.Решение. Проверка аксиом нормы очевидна:P1. kxkp = 0 ⇔|xk |pk = 0 ⇔ x = 0.PP2. kλxk = |αxk |pk = |λ| |xk |pk = |λ| kxkp .PPP3. kx + yk = |xk + yk |pk 6 |xk |pk + |yk |pk = kxkp + kykp .Выведем матричную норму, согласованную с данной, а именно, положим:n1 XkAkp = max|akj | pk .jpjk=1Покажем, что эта норма согласована с векторной нормой k·kp . Действительно,kAxkp =Xj,k|akj | |xj | pk =X 1|akj | pk |xj | pj 6 kAkp · kxkp .pjj,kС другой стороны, рассматривая её на базисных векторах ej , для которых kej kp = pj , получаемkAej kp =Xkто есть kAej kp = kAkp · kej kp . |akj | pk ,Задача 17. Пусть A = AT > 0. Доказать, что итерационный методxn+1 = xn − 0.5τ A(xn+1 + xn ) − 2b6сходится при любом τ > 0 к решению системы линейных алгебраических уравнений Ax = b.

Оценить скоростьсходимости метода, если известны λmin (A) и λmax (A).Решение. Полагая rn = xn − x, имеем11rn+1 = (E − τ A)(E + τ A)−1 rn =: Brn .22По лемме об отображении спектра, собственные значения оператора B имеют видµk =1 − 21 τ λk2=− 1,1 + 12 τ λk1 + 12 τ λkk = 1, . . . , n.В силу положительности λk отсюда немедленно следует сходимость метода. Скорость сходимости можно оценитьследующим образом: krn k 6 q n r0 ,гдеЗадача 18. Пусть 22, .q = max −1−1111 + 2 τ λmin1 + 2 τ λmax20.3 0.50.4 .A = 0.1 30.1 0.1 4.8Показать, что итерационный метод xn+1 = (I − τ A)xn + τ b сходится при τ ∈ (0, 0.4).Решение. Полагая rn = xn − x, имеемrn+1 = (E − τ A)rn .Для локализации собственных значений матрицы A воспользуемся следующей теоремой:Теорема 1 (Гершгорин).

Для всякой матрицы A ∈ Mn справедливо соотношение:σ(A) =n[i=1{z ∈ C : |z − aii | < Ri′ (A)},где σ(A) = λ1 , . . . , λn — множество собственных значений матрицы A (спектр), иRi′ (A) =nXj=1,j6=i|aij |.Более того, если объединение k из этих кругов есть связная, не пересекающаяся с остальными кругами область, то в ней содержится ровно k собственных значений.Указанные в теореме области для матриц A и AT соответственно будут выглядеть следующим образом:Рис. 17Рис. 2Матрица A вещественна, поэтому таковым является и её характеристический многочлен.

Следовательно, еёсобственные значения должны разбиваться на комплексно сопряжённые пары. Однако, круги на втором рисункене пересекаются, то есть в каждом из них должно лежать ровно одно собственное значение, откуда немедленнополучаем, что все собственные значения матрицы A — вещественные и лежат на отрезке [1.8, 5].

Теперь несложнополучить требуемую оценку для собственных значений матрицы E − τ A:1 > 1 − 1.8τ > 1 − τ λk > 1 − 5τ > −1,значит, имеет место сходимость. Задача 19. Пусть собственные значения матрицы A удовлетворяют условиям λ1 ≈ −1; λk ∈ [1, 5] приk = 2, 3, . . . . Для решения системы уравнений Ax = b выписать сходящийся итерационный метод типа методаРичардсона с переменными параметрами.Решение. Общий вид метода Ричардсона:xn+1 = xn − (αA + β)(Axn − b).Полагая rn = xn − x, имеемrn+1 = (E − βA − αA2 )rn .(1)По лемме об отображении спектра, собственные значения этой матрицы имеют вид 1 − βλk − αλ2k . Получаемусловие сходимости метода Ричардсона:|1 − βλk − αλ2k | < 1.Оно выполняется, в частности, при α =113 ,β = 0. Задача 20.

Пусть λ1 , . . . , λm — известные собственные значения матрицы A. Выписать метод простойитерации с переменным шагом τk , который через m шагов давал бы точное решение системы Ax = b.Решение. Общий вид метода простой итерации с переменным шагом:xn+1 = xn − τn (Axn − b).Полагая rn = xn − x, имеемrn+1 = (E − τn A)rn ,Полагая τn =1λn ,rm =m−1Yn=0(E − τn A)r0 .получим, что все собственные значения матрицыm−1Qn=0mравенство нулю всей матрицы, а значит и нужное нам равенство r(E − τn A) будут нулевыми, что означает= 0. 3Задача 21. Выяснить, к какому из корней уравнения x −x = 0 в зависимости от начального приближенияx0 сходится метод Ньютона. Возможна ли расходимость?Задача 22. Найти порядок аппроксимации разностной схемыun+1 − 2un + un−1un+1 + 2un + un−1=,2h4краевой задачи(u′′ = u,u(0) = u(1) = 0и исследовать её на устойчивость.8u0 = uN = 0Решение.

Рассмотрим решение u и разложим его в ряд Тейлора:11h3 + O(h4 ),un+1 = un + u′n h + u′′n h2 + u′′′26 nи, аналогично,11un−1 = un − u′n h + u′′n h2 − u′′′h3 + O(h4 ).26 nПодставляя эти выражения в схему, получимu′′n + O(h2 ) = un +u′′n+ O(h4 ),4откуда следует, что порядок аппроксимации равен O(h2 ) (первые слагаемые слева и справа уничтожаются всилу уравнения).Исследуем схему на устойчивость с помощью спектрального признака. Подставим un = λn и найдём собственные значения разностного оператора.λ2 − 2λ + 1λ2 + 2λ + 1=.h24Получили характеристический многочлен:h2h2h221−λ −2 1+λ+ 1−= 0.444Находим корни:λ1,2h2±=1+4s2 22h2h2hh2− 1−=1+±h= 1±.1+4442Для того, чтобы была выполнена α-устойчивость, нужно1 ± h 6 1,2что, очевидно, не выполнено.

Однако имеется устойчивость в том смысле, что спектральный радиус ограниченвеличиной 1 + Ch для некоторого C. В самом деле, достаточно взять C = 2:2h1±6 1 + 2h2при достаточно малом h. На самом деле, как легко видеть, в качестве константы C можно взять любое число,строго большее 1. Задача 23. Аппроксимирует ли конечно-разностная схемаun+1 − 3un + un−1− fn = 02hуравнение u′ = f (x, u)?Решение.

Подставим точное решение в схему, разложенное по Тейлору:1un+1 = un + u′n h + u′′n h2 + O(h3 ),2и, аналогично,1un−1 = un − u′n h + u′′n h2 + O(h3 ).2Получим1un + O(h2 ) − fn = 0,2hоткуда следует, что никакой аппроксимации не наблюдается. −Задача 24. Для краевой задачи∆u = f,u=u=u= 0,y=0y=1x=1 ∂u∂ν = 0 при x = 09выписать разностную схему с порядком аппроксимации O(h2 ) и предложить метод решения получающейсясистемы линейных уравнений.Решение. В нашем случаечто схема∂u∂ν= − ∂u∂x (знак учитывает направление внешней нормали). Несложно проверить,unm+1 − 2unm + unm−1un+1− 2unm + un−1mmn+= fm.h2h2даёт порядок аппроксимации O(h2 ), не будем повторять те же выкладки, поскольку проверка делается стандартным образом — разложением по Тейлору нецентральных узлов до нужного порядка и подстановкой в схему.Далее, нужно учесть граничные условия:unm = 0 при n = N или m = 0 или m = M.Теперь нужно включить в схему последнее граничное условие на нормаль.αu2m + βu1m + γu0m =Разлагая снова по Тейлору, получаем(α + β +γ)u0m∂u 0 +O(h2 ).∂x m∂u 0βh2 ∂ 2 u 02+ (2hα + βh) + 2h α + +O(h2 ) = 0.∂x m2∂x2 mЧтобы аппроксимация таки была, потребуем равенства нулю всех коэффициентов в левой части.

Получаемсистемуα + β + γ = 0,2hα + βh = 1,2 22h α + βh2 = 0.Отсюда находимβα=− ,4β1= ,2h213, α=− , γ=− .h2h2hПодставляя найденные коэффициенты, получаем схему для краевого условия на нормаль:β=−u2m + 4u1m − 2u0m= 0.2hПроанализируем полученную схему. Ясно, что мы получаем 5-диагональную матрицу, которую можно решать методом прогонки или методом стрельбы. Вообще говоря, можно применять и оптимизированный дляленточных систем алгоритм Гаусса. Задача 25. Для начально-краевой задачиut = uxx + f (x, t),u(x, 0) = u (x),0∂u=0приx = 0, ∂νu(1, t) = 0построить разностную схему с порядком аппроксимации O(h2 + τ 2 ), которая на каждом шаге по временитребовала бы решения системы уравнений с трёхдиагональной матрицей.u0mРешение.

Характеристики

Список файлов ответов (шпаргалок)