1631124688-fb0b2564726fdb4c51612f2aa6ab974b (848587), страница 2

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

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

. . , ik−1 +1; v̂ik−1 +1 =,bik−1 +1 −cik−1 +1 ·βik−1+2v̂i = β̂i v̂i−1 , i = ik−1 + 2, . . . , ik − 1,−ãk vik−1 + b̃k vik − c̃k vik+1 = f˜k ,b̃k = bik − aik vik −1 − cik v̂ik +1 ,ãk = aik v̂ik −1 ,c̃k = cik v̌ik +1 ,f˜k = fik + aik ṽik −1 + cik ṽik +1 .28(7)МЕТОД ЦИКЛИЧЕСКОЙ РЕДУКЦИИнечетные узлычетные узлы29УСТОЙЧИВОСТЬ МЕТОДОВ ПРОГОНКИМатрица положительного типа: неразложимость,свойство диагонального преобладания, положительностьдиагональных и неположительность внедиагональныхэлементовУтверждение 1: метод прогонки для решения СЛАУс трехдиагональной матрицей положительного типаявляется β-устойчивым (0 ≤ βi ≤ 1).Ṽi+1 = Vi+1 + δi+1 ⇒ Ṽi = βi (Vi+1 + δi+1 ) + zi ,|δi | ≤ δ ⇒ |δi | ≤ δi+1 ≤ δ.Утверждение 2: рассмотренные редуцированные СЛАУявляются трехдиагональными системами положительноготипа, если таковыми являются исходные СЛАУ.30ПОСТАНОВКИ НАЧАЛЬНО-КРАЕВЫХ ЗАДАЧ∂u+ L(u) = f (~x , t), ~x ∈ Ω ⊂ Rd , d ≥ 2,∂tΩ̄ = Ω ∪ Γ, 0 < t ≤ Te < ∞, u |t=0 = u 0 (~x ),(8)l(u) |Γ = g (~x , t), ~x = (x1 , .

. . , xd ),!nnXX∂∂u∂uLu = −ai,j (~x )+bi+ cu = f (~x ). (9)∂x∂x∂xijii,j=1i=1α k u + βkdXi,j=1ai,j∂ucos(~n, xj ) = gk , |αk | + |βk | =6 0, ~x ∈ Γk ,∂xj(10)31ПРОСТРАНСТВЕННО-ВРЕМЕННЫЕ АППРОКСИМАЦИИB u̇ h + Au h = f h ,u̇ h , u h , f h ∈ RN ; B, A ∈ RN,N ,(11)f h = {fl }, B = {bl,l }, A = {al,l }, u h = {ulh }, (u)h = {u(~xl )}B(u̇)h + A(u)h = (f )h + ψ h , ψ = O(hγ ),X(Au h )l ≡ al,l ul +al,l 0 ul 0 = fl , l ∈ Ωh ,l 0 ∈ωll = 1, .

. . , N, Nl N, N ≈ 107 − 1010 , Nl ≈ 10 ÷ 3032(12)(13)ЯВНЫЕ И НЕЯВНЫЕ СХЕМЫBu n+1 − u n+ θ(Au n+1 − f n+1 ) = (1 − θ)(f n − Au n ),(14)τnθ ∈ [0, 1], n = 0, 1, . . . ,θ = 1/2 ψ τ = O(τ 2 ), τ = maxn {τn }, ψ n = ψ τ + ψ hB(u)n+1 − (u)n+θ[A(u)n+1 −(f )n+1 ] = (1−θ)[(f )n −A(u)n ]+ψ n ,τn(15)ũr n = (1 − θ)(f˜n − Aũ n ) − Bn+1− ũ nτn33+ θ(Aũ n+1 − f˜n+1 ]. (16)НЕЯВНЫЕ СХЕМЫ РУНГЕ – КУТТЫ – РАДО, IРАЗРЫВНЫЕ МЕТОДЫ ГАЛЕРКИНА ДЛЯ ОДУ∂t u(t) + Au(t) = f (t), t ∈ (0, T ), u(0) = uo ,u, f ∈ RNh , A ∈ RNh ,Nhuτn+1 ∈ PNτ (tn , tn+1 ), vτn+1 ∈ PNt (tn , tn+1 )tRn+1−uτn+1 (t)∂t vτn+1 (t)dt + uτn+1 vτn+1 (tn+1 )+AtntRn+1uτn+1 (t)vτn+1 (t)vτn+1 (t)dt =tntRn+1f (t)dt + uτn (tn )vτn+1 (tn )tn34НЕЯВНЫЕ СХЕМЫ РУНГЕ – КУТТЫ – РАДО, II(Kr + AMτ )u n+1 = f n+1 + Cτ u n , n = 0, 1, ..., N − 1tRn+1f (t)Ψnl (t)dt},u n+1 ∈ RNt ∗Nh , f n+1 = {fl n+1 =tntRn+1tnf (t)dt ≈ rsPbk f (tn + ck τ ), c1 = 0.k=1Теорема.

Разрывные схемы Галеркина Nt -го порядка дляОДУ эквивалентны (Nt + 1)-стадийным неявным методамРунге-Кутты с квадратурами Радо, которые являютсяА-устойчивыми алгоритмами и имеют погрешность 2Nt + 135ВЫБОР НАЧАЛЬНОГО ПРИБЛИЖЕНИЯа) Простой сносu n+1,0 = u n + O(τ )б) Линейная экстраполяцияu n+1,0 = u n + (u n − u n−1 )τn /τn−1 + O(τ 2 ),в) Схема предиктор-корректорB(û n+1 − u n ) = τn (f n − Au n ) ≡ τn r n ,u n+1,0= û n+1s = 1, . .

. , m : B(u n+1,s −u n ) = τn [θ(f n+1 −Au n+1,s−1 )+(1−θ)(f n −Au n )],r n+1,s = τn [θ(f n+1 −Au n+1,s−1 )+(1−θ)(f n −Au n )]−B(u n+1,s −u n ) ≤ ε36МИНИМИЗАЦИЯ НАЧАЛЬНОЙ НЕВЯЗКИq-шаговый метод наименьших квадратовu n+1,0 = u n + c1 v1 + . . . + cq vq = u n + Vc,vl = u n − u n−l , l = 1, . . . , q,c = (c1 , . . . , cq )> ∈ Rq ,V = (v1 , . .

. , vq ) ∈ RN,q .Cu n+1 ≡ (τn−1 B + θA)u n+1 = g n+1 ,g n+1 = [τn−1 B + (1 − θ)A]u n + θf n+1 + (1 − θ)f n .r n+1,0 = r n − CVc, r n = g n+1,0 − Cu n+1,0 ,37МНК С ИТЕРАЦИОННЫМ УТОЧНЕНИЕМr n+1,0 ≈ 0 : Wc ≡ CVc = r n ,W ∈ RN,q ,Gc ≡ W T Wc = W > τ n , G = V > C > CV ∈ Rq,q ,u n+1,m = rn B −1 (gn − θAu n+1,m−1 ),kr n+1,m k = kg n − Cu n+1,m k ≤ εkg n k,ε 1, u n+1 = u n+1,m .38ОБЩЕЕ ПРЕДСТАВЛЕНИЕ ИТЕРАЦИОННЫХ МЕТОДОВПервая каноническая форма итерационногометодаBn (u n − u n−1 ) = f − Au n−1Bn – предобусловливающие матрицы.Вторая каноническая форма итерационногометодаu n = Tn u n−1 +gn , Tn = I −Bn−1 A, Bn = A(I −Tn )−1 −матрицы перехода (итерационного шага).Стационарные итерационные процессы:Bn ≡ B, Tn ≡ T .39СЕТОЧНАЯ ПРЯМОУГОЛЬНАЯ ОБЛАСТЬ(Au)i,j = ei,j ui,j −ai,j ui−1,j −bi,j ui,j−1 −ci,j ui+1,j −di,j ui,j+140МОДЕЛЬНАЯ ЗАДАЧА ДИРИХЛЕhyhx(−vi−1,j +2vi,j −vi+1,j ) + (−vi,j−1 +2vi,j −vi,j+1 ) =hxhyv0,j= hx hy fi,j , i = 1, 2, .

. . , i,j = 1, 2, . . . , j,= g0,j , vi,j = gi,j , vi,0 = gi,0 , vi,j = gi,j , i, j = i, ..., N.A = A1 + A2при hx = hy000(ei,j = ei,j+ ei,j)000ei,j= ei,j=2pπ, p = 1, ..., N,2(N + 1)h2 ≈rλ1 < λN ≈ 4(1 − h2 ), Cond(A1,2 ) ≈ 4h−2 ,2πzp,q (i, j) =(Sin pih+Sin qjh), h =, p, q = 1, ...NN +1N +1λp (A1,2 ) = 4Sin241БЛОЧНЫЕ (НЕЯВНЫЕ) ИТЕРАЦИОННЫЙ МЕТОДЫA = D − L − U, D = Di – блочно-диагональная,L – нижняя, U – верхняя треугольная матрицы.(Du)i = {ei,j ui,j − bi,j ui,j−1 − ci,j ui,j+1 : j = 1, . . . , J}Блочный метод Якобиu n+1 = D −1 (f + Lu n + Uu n ), n = 0, 1, . .

.Неявный метод чебышевского ускоренияu n+1 = u n + τn D −1 (f − Du n + Lu n + Uu n ) == (1 − τn )u n + τn D −1 (f + Lu n + Uu n )ОБЩИЕ ХАРАКТЕРИСТИКИ ИТЕРАЦИОННЫХМЕТОДОВz n = u − u n – вектор ошибки,ρ = ||Tn || – коэффициент подавления ошибки.n → ∞ : u n → u, u = Tn u + g n , z n+1 = Tn z n||z n+1 || ≤ ||Tn ||·||z n || ≤ ρn ||z n || ≤ ρn+1 ||z 0 ||, ρn ≤ ρ.Средняя скорость сходимости итерацийn kz n kn −1 kz n k ooRn = maxln 0 , n(ε) = min n : 0 ≤ ε .nkz kkz kz 0 6=0Критерий останова: ||r m || ≤ ε||f ||Оценка итерационной ошибки:||δ m || = ||u − u m || ≤ ||A−1 || · ||r m ||43МЕТОД ЧЕБЫШЕВСКОГО УСКОРЕНИЯа) Двухчленный периодический процессu n+1 = u n + τn r n , r n = f − Au n , n = 0, 1, ...;(2n−1)πτn = 2/ λN +λ1 −(λN −λ1 ) cos, n = 1, . .

. , m;2mλN + λ1λ1 + λN − 2λ .Tm;Pm (λ) = TmλN − λ1λN − λ1√n(εm ) 6 0, 5|ln(εm /2)| C + 1, C = λN /λ1 .Устойчивость вычислений: специальнаяупорядоченность итерационных параметров44б) Трехчленные чебышевские формулыu 1 = u 0 + τ r 0 , τ = 2/(λ1 + λN ), n = 1, 2, ... :r n = f − Au n , u n+1 = u n + γn τ r n + (γn − 1)(u n − u n−1 ),γn = 4/(4 − γn−1 γ 2 ), γ0 = 2, γ = (C − 1)/(1 + C ).Pn+1 (λ) = γn (1 − τ λ)Pn (λ) + (1 − γn )Pn−1 (λ),P0 (λ) = 1, P1 (λ) = 1 − τ λ.в) Связанные двухчленные рекурсииp 0 = r 0 = f − Au 0 , n = 1, 2, ... :u n = u n−1 + αn−1 p n−1 ,r n = r n−1 − αn−1 Ap n−1 ,p n = r n + βn p n−1 .α0 = τ,αn = γn τ,βn = (γn − 1)αn−1 /αn .45МЕТОДЫ ЗЕЙДЕЛЯ И ВЕРХНЕЙ ПОСЛЕДОВАТЕЛЬНОЙРЕЛАКСАЦИИu n = ωD −1 (f +Lu n +Unn−1 )+(1−ω)u n−1 , 0 < ω < 2T (ω) = (D−ωL)−1 (1−ω)D+ωU , B(ω) = D−ωL.Явные методы последовательных смещенийωnn−1ukn =(fk −ak,1 u1n −.

. .−ak,k−1 uk−1−ak,k+1 uk+1−. . .ak,k−ak,N uNn−1 ) + (1 − ω)ukn−1 , k = 1, . . . , N.Блочные (неявные) методыnn−1ukn = ωDk−1 (Lk uk−1+uk+1)+(1−ω)ukn−1 , k = 1, . . . , N.46НЕЯВНЫЕ МЕТОДЫ ПЕРЕМЕННЫХ НАПРАВЛЕНИЙ.АЛГОРИТМ ПИСМАНА – РЕЧФОРДАA = A1 + A20 < m ≤ λ(A1 ), λ(A2 ) ≤ Mu n−1/2 = u n−1 − τn (A1 u n−1/2 + A2 u n−1 − f ),u n = u n−1/2 − τn (A1 u n−1/2 + A2 u n − f ).2τn = τ0 = √: ρ ≈ 1 − 2h,mMОптимальная последовательность τn1.554.при A1 A2 = A2 A1 : R ≈| ln h|47МЕТОД КАЧМАЖА(Au)i = (u, Ati ) = Ai u = fi ,u n,i = u n,i−1 + Ati rin,i−1 ,Ai Ati = (Ati , Ati ) =NXi = 1, 2, . .

. , N,i = 1, 2, . . . , N,2ai,j= 1,u n = u n,N ,i = 1, 2, . . . , N.j=1Иллюстрация сходимости метода Качмажа для N = 248БЛОЧНЫЙ МЕТОД КАЧМАЖАfp = fi , i = (p − 1)m + 1, . . . , pm ,Ap = Ai , i = (p − 1)m + 1, . . . , pm .Ap u = fp , p = 1, 2, . . .

, l.n,p−1u n,p = u n,p−1 + ωA+,p rpn = 1, 2, . . . , p = 1, 2, . . . , l, u n = u n,l ,tt −1A+p = Ap (Ap Ap ) .49МЕТОД ЧИММИНОГеометрическая интерпретация метода Чимминос экстраполяциейN1 X >nn−1−1n−1u =u+A (Ai A>)i ,i ) (f − AuN i=1 inu =un−1+ ωl−1lX> −1n−1A>).p (Ap Ap ) (fp − Ap up=150ВЗВЕШЕННЫЕ МЕТОДЫ ЧИММИНО> −1 nr n = f − Au n , u n,p = A>p (Ap Ap ) r , p = 1, ...mu n+1 = u n + c1 v1n + ... + cm vmn , vpn = u n − u n,pr n+1 = r n − c1 w1n − ... − cm wmn , wpn = Avpnr n+1 = r n − AVn c̄ n , Vn = {vpn } ∈ RN,mWn c̄ n ≡ AVn c̄ n = r n , Vn> AVn ĉ n = Vn> r n ,Метод наименьших квадратовWn> Wn č n = Wn> r n : min(r n+1 , r n+1 )51ИНТЕРАЦИОННЫЕ МЕТОДЫВ ПОДПРОСТРАНСТВАХ КРЫЛОВАAu = f ,A = {al,m } ∈ RN,N ,(Av , v ) ≥ δ||v ||2 ,δ > 0,u = {ul },(v , w ) =NXf = {fl } ∈ RN ,vi wi ,||v ||2 = (v , v ),i=1>A 6= A в общем случае.Мультипредобусловленные методы полусопряженныхнаправленийr 0 = f − Au 0 ,n = 0, .

. . : u n+1 = u n + Pn ᾱn ,r n+1 = r n − APn ᾱn = r q − APq ᾱq − · · · − APn ᾱn ,nPn = (pqn , . . . , pM) ∈ RN,Mn ,n0 ≤ q ≤ n,ᾱn = (αn,1 , . . . , αn,Mn )> ∈ RMn .52ОРТОГОНАЛЬНЫЕ СВОЙСТВАНАПРАВЛЯЮЩИХ ВЕКТОРОВ0(γ)00(γ)k,k(Apkn , Aγ pkn0 ) = ρn,k δn,n0,ρn,k = (Apkn , Aγ pkn0 ),γ = 0, 1, n0 = 0, 1, . . . , n,Минимизация функционалаk, k 0 = 1, 2, . . . , Mn ,n PMnPn+1Φ(γ)) ≡ (r n+1 , Aγ−1 r n+1 ) = (r q , Aγ−1 r q )−n (rαn,l = σn,l ρ(γ)n,n ,Подпространства Крылова(r q , Aγ plk )2k=q l=1(γ),ρk,lσn,l = (r 0 , Aγ pln ).0nKn = Span{r 0 , Ap10 , ..., ApM, ..., Ap1n , ..., ApM}, M = 1+M0+· · ·+Mnn053РЕКУРСИИ ДЛЯ ВЫЧИСЛЕНИЯНАПРАВЛЯЮЩИХ ВЕКТОРОВMkn XX(γ)n+1−1n+1pl = Bn+1,l r −βn,k,l plk , n = 0, 1, ...;k=0 l=1N,NBn,l ∈ R , l = 1, ..., Mn ; γ = 0, 1,>(γ)(γ)(γ)(γ)β̄n,k = {βn,k,l } = βn,k,1 .

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

Список файлов лекций