Das zentrale Differenzierungsschema für die zweite Ableitung führt zu einer schlechten Konditionierung

8

Das zentrale Differenzschema: ergibt eine tridiagonale Koeffizientenmatrix [ 1 -2 1]; Wenn die Anzahl der Punkte größer wird, wird diese Matrix schlecht konditioniert. Dies ist jedoch eine populäre Diskretisierung. Warum wird dieses Schema so häufig verwendet, wenn es zu einer schlechten Konditionierung neigt, und was ist die typische Problemumgehung für die schlechte Konditionierung?

d2udx2=un+12ui+un1Δx2
ben142
quelle

Antworten:

16

TL; DR: Der kontinuierliche Operator zeigt dieses Verhalten, jede getreue Diskretisierung wird es einfach erben.

Tieferer Schnitt: Wenn Sie das Spektrum (Eigenpaare) des stetigen Operators , sind die Eigenvektoren trigonometrische Funktionen der Form und mit Eigenwert . Niederfrequenzfunktionen (dh konstante oder sehr glatte Funktionen) können in jedem Gitter gut dargestellt werden. Wenn Sie mehr Punkte verfeinern und abtasten, werden Sie auch die Hochfrequenzlösungen genauer approximieren. Daher hat grundsätzlich jede Diskretisierung dieses Operators einen nahezu konstanten -Eigenwert und einen -Eigenwert, der quadratisch mit der Anzahl der Abtastwerte wächst (also eine Bedingungsnummer cos(kx)sin(kx)k2λminλmaxκ=λmax/λmind2dx2cos(kx)sin(kx)k2λminλmaxκ=λmax/λmindas wächst quadratisch mit N). Sie können diesem Schicksal also nicht wirklich entkommen, indem Sie einfach mit FD-Schemata im Vergleich zu FE-Schemata usw. herumspielen.

Dies ist problematisch für (z. B.) Krylov-Löser oder andere Techniken, deren Konvergenz von der Bedingungsnummer abhängt (und daher mehr als lineare Zeitkomplexität benötigt, um dieses Problem zu lösen). Sie können das Problem jedoch mithilfe einer Multiresolution-Analyse umgehen (insbesondere Multigrid, mit dem dieses Problem gelöst werden kann, und viele andere, die es mögen, in -Zeit). Die Konvergenzeigenschaften von Multigrid basieren alle auf dieser Art von Spektral- / Fourier-Analyse.O(N)

rchilton1980
quelle