---

bruger lidt matlabsyntax, da det ellers er ret ulæseligt

Jeg læser at et udtryk på formen Ax=b kan løses itterativt ved at gætte på
en x og derefter beregne
x_k+1 = Gx_k+c hvor G og c findes ved at definere A som M-N hvor M ikke er
singulær
G=inv(M)N og c=inv(M)b

Jeg fandt på et eksempel med A=[1 2;3 4]; og b=[4;5]
Det giver en løsning for x på [-3;3.5];

For ikke at starte lige ved målet så gætter jeg på en x_k=[2;2];

jeg får derefter en sekvens af x, som ses herunder. Det er muligt jeg er
pessimistisk, men det ser altså ikke ud til at x nærmer sig løsningen. Hvad
er problemet her? Laver jeg en fejl, eller virker metoden bare ikke for
andet end ret gode gæt?

>> x=G*x+c

x =

-20
7

>> x=G*x+c

x =

58
-10

>> x=[2;2];
>> x=G*x+c

x =

-20
7

>> x=G*x+c

x =

58
-10

>> x=G*x+c

x =

-220
51

>> x=G*x+c

x =

770
-166

>> x=G*x+c

x =

-2756
607

>> x=G*x+c

x =

9802
-2146

>> x=G*x+c

x =

-34924
7659

>>

---

> x_k+1 = Gx_k+c hvor G og c findes ved at definere A som M-N hvor M ikke er
> singulær
> G=inv(M)N og c=inv(M)b

Jeg glemte lige at skrive hvad jeg fandt på til M og N
M=[1 4; 2 7]; N=[0 2;-1 3];
så det er opfyldt at A=M-N;
det giver en G=[-4 -2; 1 1]; og c=[-8;3]'

---

"Jens N" <jens@nej.tak> writes:

> bruger lidt matlabsyntax, da det ellers er ret ulæseligt Jeg læser
> at et udtryk på formen Ax=b kan løses itterativt ved at gætte på en
> x og derefter beregne x_k+1 = Gx_k+c hvor G og c findes ved at
> definere A som M-N hvor M ikke er singulær G=inv(M)N og c=inv(M)b

Jeg gætter på at du skal vælge N således at absolutværdierne af G's
egenværdier er mindre end 1. Det følgende virker i Octave (en
opensource klon af Matlab).

octave:22> A=[1 2;3 4]; b=[4;5];N=[0 0.2;-0.1 0.3];M=A+N; G = M^(-1) * N;c = M^(-1) * b;x0=[2;2];x1=G*x0+c;x2=G*x1+c;x3=G*x2+c
x3 =

-3.0026
3.5000

octave:23> A^(-1) * b
ans =

-3.0000
3.5000

octave:24> eig(G)
ans =

-0.084690
0.113536

Jeg sådan set kun regnet på om metoden kan bruges til at løse et
ligningssystem på følgende form

Ax=0.

Jeg antager at A har fuld rang, så ligningen har kun en løsning,
nemlig x=0. Desuden får du c=0, så din iterationsformel kommer til at
se sådan her ud:

x_(k+1) = G x_k

Denne ligning konvergerer kun hvis absolutværdierne af G's egenværdier
er strengt mindre end 1 (Det kan man vise ved at opskrive x i en basis
a egenvektorer til G).

---

> Jeg gætter på at du skal vælge N således at absolutværdierne af G's
> egenværdier er mindre end 1. Det følgende virker i Octave (en
> opensource klon af Matlab).
>
> octave:22> A=[1 2;3 4]; b=[4;5];N=[0 0.2;-0.1 0.3];M=A+N; G = M^(-1) * N;c
> = M^(-1) * b;x0=[2;2];x1=G*x0+c;x2=G*x1+c;x3=G*x2+c
> x3 =

hvis man alligevel skal til at beregne egenværdierne, kan man så ikke lige
så godt løse ligningen absolut ved at beregne inv(A)?
Er der en nem måde at finde en passende N der opfylder kravene?
Min tekst siger nu heller intet om kravet for egenværdier. Det ser
imidlertid ud til at din løsning virker, hvor min ikke gør

---

"Jens N" <jens@nej.tak> writes:

>> Jeg gætter på at du skal vælge N således at absolutværdierne af G's
>> egenværdier er mindre end 1. Det følgende virker i Octave (en
>> opensource klon af Matlab).
>>
>> octave:22> A=[1 2;3 4]; b=[4;5];N=[0 0.2;-0.1 0.3];M=A+N; G = M^(-1) * N;c
>> = M^(-1) * b;x0=[2;2];x1=G*x0+c;x2=G*x1+c;x3=G*x2+c
>> x3 =
>
> hvis man alligevel skal til at beregne egenværdierne, kan man så
> ikke lige så godt løse ligningen absolut ved at beregne inv(A)? Er
> der en nem måde at finde en passende N der opfylder kravene? Min
> tekst siger nu heller intet om kravet for egenværdier. Det ser
> imidlertid ud til at din løsning virker, hvor min ikke gør

Hvis du vælger N og M som henholdsvis øvre og nedre trekantsmatricer,
så får du så vidt jeg kan se en metode der hedder Gauss-Seidel. Jeg
ved ikke om den altid vil konvergere, og jeg ved ikke om den er den
bedste på markedet, men det afhænger vel også af hvilket problem du
vil løse.

http://mathworld.wolfram.com/Gauss-SeidelMethod.html

Hvis du ikke sørger for at M er en pæn matrice, så er du nødt til at
løse et ligningssystem (M c = b) for at finde c. Dette problem ef lige
så svært som Ax = b.

Jeg kan forresten varmt anbefale gruppen sci.math.num-analysis. Der
sidder nogle store guruer og løser folks problemer. Hvis du sørger for
at give detaljer nok (sparse, symmetrisk, dimension osv), så får du
et detaljeret svar.

Held og lykke

Niels

---

> Hvis du ikke sørger for at M er en pæn matrice, så er du nødt til at
> løse et ligningssystem (M c = b) for at finde c. Dette problem ef lige
> så svært som Ax = b.
>
> Jeg kan forresten varmt anbefale gruppen sci.math.num-analysis. Der
> sidder nogle store guruer og løser folks problemer. Hvis du sørger for
> at give detaljer nok (sparse, symmetrisk, dimension osv), så får du
> et detaljeret svar.

Takker for dit feedback. Jeg har nu intet konkret problem som skal løses.
Jeg sad bare og læste (lektier). Da jeg ville afprøve en beskrevet metode,
kunne jeg ikke få den til at konvergere og så undrede jeg mig lidt.
Jeg kunne sikkert også bare være tålmodig og se hvad der står i næste
kapitel

---

"Jens N" <jens@nej.tak> writes:

> Jeg læser at et udtryk på formen Ax=b kan løses itterativt ved at gætte på
> en x og derefter beregne
> x_k+1 = Gx_k+c hvor G og c findes ved at definere A som M-N hvor M ikke er
> singulær
> G=inv(M)N og c=inv(M)b

Ja det er en "stationary iterative method". Forskellige smarte valg af M
og N giver dig forskellige metoder.


Opsplitningen af A i M og N indsat i den oprindelige ligning:
(M-N)x = b flyttet rundt:
Mx = Nx +b

Så får man ideen at man kan bruge det til iteration:
Mx_k+1 = Nx_k + b

Ender man med x_k+1 = x_k (inden for en tolerance) er løsningen fundet,
og man kan lave en iteration ved (Matlabnotation):

x_k+1 = M \ (Nx_k + b)

Eller ved at invertere M, gange igennem, og få dit udtryk.

Men bare fordi man har gjort det, kan man ikke forvente konvergens, der
skal opsplitningen vælges rigtigt.

Det er i øvrigt vigtigt at M skal vælges så den ligning er markant
lettere at løse end det oprindelige system/M er nem at invertere.

> er problemet her? Laver jeg en fejl, eller virker metoden bare ikke for
> andet end ret gode gæt?

Hvis du vælger M til at være diagonalen af A får du Jacobiiteration.
Hvis du vælger den nedre trekant (incl. diagonal) får du
Gauss-Seidel. Gauss-Seidel kan udvides med en relaksationsparameter, som
giver SOR (Successive Overrelaxation).

Her er en gennemgang af metoderne:
ftp://netlib2.cs.utk.edu/linalg/templates2.tgz

Du kan også finde en matlabimplementation af dem på netlib.


Mvh.


Dennis Jørgensen

---

> Men bare fordi man har gjort det, kan man ikke forvente konvergens, der
> skal opsplitningen vælges rigtigt.
>
> Det er i øvrigt vigtigt at M skal vælges så den ligning er markant
> lettere at løse end det oprindelige system/M er nem at invertere.

Ok, den del nævnte min bog desværre ikke. Man skulle bare sørgre for at
A=M-N, hvilket jo var nemt nok.
At vælge en M som er øvre eller nedre trekant og en N som opfylder
ligningen, er jo nemt nok... bare man husker at gøre det.