Osnovna tema 🙂 Napisao sam program za notepad koji implementira metodu ponderisanog rezidua u Mathematici. Pokazalo se prilično zanimljivo, postoji prostor za eksperimente u promjeni funkcija testa i težine.

Metoda ponderisanog ostatka: Algoritam

Problem koji se rješava metodom ponderisanog ostatka

Na primjer, uzmimo problem iz knjige “The Finite Element Method Using MATLAB” od Kwon, Bang (str. 31).

Metoda ponderisanog ostatka u Mathematici

Integrali neće biti prikazani na web stranici, pa tekst predstavljam u obliku slike:

Metoda ponderisanog ostatka - tekst u svesci Mathematica bez izlaznih ćelija.

Prema tekstu. U prva tri reda definira se rezidualna funkcija, zatim se bira test funkcija s parametrom, a zatim se rezidual izračunava zamjenom test funkcije.

Zatim se prvo implementiraju tri metode - metoda kolokacije, a zatim metoda najmanjih kvadrata i metoda Galerkina. Za kolokaciju, točka uzorkovanja je . Za svaku od ovih metoda postavlja se vlastita funkcija ponderiranja, a testna funkcija ostaje ista. Izračunava se ponderisani rezidual—integral u domenu rješenja problema proizvoda težine funkcije i ostatka. Integraciju vrši , ali naš izraz pod integralom uključuje parametar test funkcije. Dakle, nakon integracije imamo funkciju od . Ponderirani izraz ostatka se tada postavlja na nulu i parametar se određuje. Tako testna funkcija postaje specifična funkcija samo jedan argument.

Predavanje 6

Metoda ponderisanog ostatka

Metoda ponderisanog ostatka

Metoda najmanjih kvadrata je prilično jednostavna u konceptu. Međutim, tzv ponderisana metoda ostatka. U ovoj metodi se konstruiše sistem jednačina za određivanje nepoznatih koeficijenata na sledeći način:

Evo - neki sistem funkcija “ponderiranja”. Odatle, inače, dolazi naziv „ponderisana rezidualna metoda“.

Matematičko značenje ovog pristupa je sljedeće. Imajte na umu da su integrali u (28) skalarni produkti rezidualne funkcije i težinskih funkcija. Ako koristimo geometrijsku analogiju, možemo reći da su integrali u (28) projekcije rezidualne funkcije na funkcije težine.

Kada bi bilo moguće koristiti kompletan sistem funkcija kao težinske funkcije, tada bi rezultirajuće rješenje bilo egzaktno. Međutim, prema iz očiglednih razloga, moramo koristiti konačan broj težinskih funkcija.

Zapišimo sistem (28) u odnosu na primjer koji se razmatra (1):

Odnosno, opet, kao i kod metode najmanjih kvadrata, problem se svodi na rješavanje sistema linearne jednačine. Ali elementi matrice i vektora imaju drugačiji oblik:

Sistem funkcije ponderiranja može se odabrati na različite načine. Isprobajmo prvo najjednostavniju opciju: prve tri funkcije power series:

Podsjetimo da se moramo ograničiti na samo tri težinske funkcije, jer u ovom primjeru tražimo približno rješenje u obliku linearne kombinacije tri funkcije (18), a približno rješenje (17) sadrži tri nepoznata koeficijenta: .

Zamjenom (18) i (31) u (30) dobijamo

,

i sistemsko rješenje:

Zamjenom pronađenih vrijednosti koeficijenata u (17) dobijamo

Tabela 3

x	Tačno rješenje	Metoda ponderisanog ostatka (težine funkcije: 1, x,x 2)
0.25	-0.0716449	-0.0611209
0.5	-0.1013212	-0.0780438
0.75	-0.0716449	-0.0565199

Odgovarajući grafikon je na slici 9.

Fig.9

Kao što vidimo, rezultati su se pokazali lošijima nego kada se koristi i metoda konačnih razlika i metoda najmanjih kvadrata. Razlog za ovu nevolju nije u tome što je metoda ponderiranih ostataka loša. Činjenica je da je sistem težinskih funkcija odabran loše. Kao što je već pomenuto, u „Matematičkoj digresiji“ (drugi pasus ovog odeljka) ove funkcije nisu ni normalizovane ni ortogonalne. Tamo je korištenjem Gram-Schmidtove metode dobijen ortonormalni sistem funkcija ekvivalentan (31). Pokušajmo sada koristiti funkcije ovog sistema kao funkcije težine:

U ovom slučaju matrica i vektor su:

a rješenje sistema je:

Kao rezultat zamjene ovih vrijednosti u (17):

Tabela 4

x	Tačno rješenje	Ponderisani rezidualni metod (ortonormalni sistem funkcije snage)
0.25	-0.0716449	-0.0717608
0.5	-0.1013212	-0.1010489
0.75	-0.0716449	-0.717608

Ovdje se može vidjeti da je naizgled neznatno poboljšanje u izboru težinskih funkcija dovelo do značajnog povećanja tačnosti približnog rješenja. Usput, imajte na umu da iako su matrice i dobivene metodom najmanjih kvadrata iu posljednjem slučaju različite, rješenja za ove linearni sistemi skoro se poklopilo. Grafikon približnog rješenja stoga nije dat. Izgledalo bi kao potpuno ponavljanje slike 8.

Yu.Ya. LEDYANKIN

METODE VAŽIVANJA STANOVNIKA, KOLOKACIJE, MOMENTI. METODA PARALELNE IMPLEMENTACIJE U JEDNOM RAČUNARSKOM TOKU RJEŠAVANJA PROBLEMA MATEMATIČKE FIZIKE

Abstract. Razvija se ideja o paralelnoj implementaciji metoda važnih nejezika, kolokacija, momenata u jednom računskom toku za razvoj problema matematičke fizike sa obradom podataka u obliku sklopivih struktura na elementima procesora, što uključuje larno množenje Predlozi metoda, opisi i ispitivanja specifičnih test slučajeva, koji će biti korisni matematičarima i programerima metoda i struktura specijalnih procesora za rješavanje problema matematičke fizike i drugih zadataka.

Ključne riječi: paralelni proračuni, pojedinačni tok proračuna, sklopive strukture podataka, problemi matematičke fizike, metoda krajnjih elemenata.

Anotacija. Razvija se ideja o paralelnoj implementaciji metoda ponderiranih reziduala, kolokacija, momenata u jednom proračunskom toku za rješavanje problema matematičke fizike uz obradu podataka u obliku. složene strukture na elementima procesora uključujući skalarni množitelj. Predložena metoda, opisana i ispitana na konkretnim test primjerima, bit će korisna matematičarima i programerima metoda i struktura specijalnih procesora za rješavanje problema matematičke fizike i drugih problema.

Ključne riječi: paralelno računanje, pojedinačna računska nit, složene strukture podataka, problemi matematičke fizike, metoda konačnih elemenata.

Abstract. Razvijena je ideja o paralelnoj implementaciji metoda ponderiranih reziduala, kolokacija, momenata u jednom računskom toku rješenja problema matematičke fizike sa obradom podataka u obliku složenih struktura zasnovanih na elementima procesora uključujući skalarni množitelj. Predložena metoda je opisana i pregledana na konkretnim primjerima ispitivanja. Biće korisno za matematičare i programere metoda i struktura posebno dizajniranih procesora za rešavanje problema iz matematičke fizike i drugih problema.

Ključne riječi: paralelno računanje, pojedinačni računski tok, složene strukture podataka, problemi matematičke fizike, metoda konačnih elemenata.

1. Uvod

Upotreba metode konačnih elemenata (FEM) za modeliranje i rješavanje problema matematičke fizike (MF) olakšana je napretkom u uvođenju računskih metoda i, posebno, ponderiranih rezidualnih metoda (WRM). Naziv MVN pokriva čitavu klasu diskretnih metoda za aproksimaciju diferencijalnih i integralnih jednačina, opisanih analitički. Osnovna svrha njihove primjene je diskretizacija analitičke jednačine i njeno svođenje na sistem algebarske jednačine, čiji proračun koeficijenata (rješavanjem sistema) daje približan, ali sa visok stepen tačnost, rešenje. U ovom slučaju koriste se dobro poznate analitičke funkcije ponderiranja, koje se često nazivaju probnim. Umjesto analitičkih funkcija, one se također mogu koristiti diskretne funkcije. Izbor različitih težinskih funkcija također određuje metodu ponderiranih reziduala, odnosno tačnost, konvergenciju i stepen složenosti.

Prelazak na nove tehnologije obrade informacija pretpostavlja i novi pristup opisu i metodama implementacije MMN. Potrebno je razmotriti glavne MMN koje, pored osnovne formulacije, uključuju metode najmanjih kvadrata (LS), momenata (MM), kolokacija (MC), Galerkina (MG) itd., opisane u. Iz prvog poglavlja preuzet je pristup rješavanju MVN problema, kao i primjeri za vrednovanje dobijenih rezultata i njihovo poređenje sa rezultatima koje su dobili autori u.

© Ledyankin Yu.Ya., 2012

ISSN 1028-9763. Matematičke mašine i sistemi, 2012, br

Cilj autora je razviti MMN za paralelnu implementaciju pri rješavanju problema matematičke fizike metodom konačnih elemenata (MKE) sa obradom podataka na nivou složenih struktura u ideologiji jedne računske niti.

Sprovođenje gore navedenih ciljeva je posvećeno ovo djelo(tačnije, ciklus

2. Osnove ponderiranih rezidualnih metoda

O nizu funkcija forme

01 (x),F2(x),...,Fn (x) (1)

tačkasti proizvod< Ф, ф >tip

< Ф1, Ф2>= J F1 (x) * F2 (x) dx (2)

za sistem probnih (baznih) funkcija a sa koeficijentima ai

a F, + a2 F2+...+an Fp = 0 (3)

Možda

li u - ^a * f. li< e. (4)

Ako definiramo operator L () kao akciju koja, kada se primijeni na datu funkciju, dovodi do pojave neke druge funkcije p

tada se za linearni operator L, pozitivno određen za sve x, može sastaviti skalarni proizvod operatora L(u) i druge funkcije v:

< L(u), v >=< и, L* (v) + J dS, (6)

gdje je S granična površina;

F, G - diferencijalni operatori, čiji je oblik određen integracijom po dijelovima;

L je operator konjugiran sa operatorom L (ako je L* = L, onda je L samo-adjugantan);

F (v) - sadrži termine sa v koji se pojavljuju u 1. fazi integracije po dijelovima;

G(u) - slično, ali sadrži pojmove sa u;

F (v) - određuje glavne granične uslove (BM);

G (u) - definira neesencijalne ili prirodne GI.

Ako je za L* = L, F(u) na S 1, G (u) - dati S2 i S1 + S2 = S< L(u), а также

u >.. > 0 za sve netrivijalne u (koje zadovoljavaju homogene granične uslove), onda radi

ponderisana metoda ostatka.

Moguće je uspostaviti numeričke procedure za približno rješenje sistema diferencijalnih (integralnih) jednačina oblika

L(u) = p, x e V sa GU; (7)

F(u) = g, x e S, (8)

gdje je £ vanjska granica područja;

i je tačno rješenje, koje je aproksimirano skupom funkcija fk():

u = X ak fk; (9)

ak - nepoznati parametri;

fk - linearno nezavisne funkcije.

Nakon zamjene (9) u (7), dobiva se funkcija greške e (ostatak):

e = b(u) - p = 0. (10)

Za tačno rešenje, e = 0, pa težimo da greška u proseku bude jednaka 0, pod pretpostavkom jednaka nuli integrali uzeti iz ostatka s nekim težinskim funkcijama

< е, w >= 0, I = 1,2,...,N, (11)

gdje je w 1 skup težinskih funkcija.

Zatim, ako su parametri ak u (9) konstantni, onda se diferencijalna jednadžba (7) svodi na sistem algebarskih jednačina. Broj nezavisnih relacija je dat brojem nepoznatih koeficijenata ak i funkcija w¡.

3. Suština predloženog pristupa sa RPM

Predloženi metod upotrebe MVN fokusiran je na implementaciju jedinstvenog tehnološkog toka (UTF) za obradu složenih struktura podataka (SDS) pri rješavanju klase MF problema i drugih u paralelnim strukturama, čiji elementi obrade (PE) sadrže skalarni množitelj (SC). Upotreba RMP-a omogućava pisanje polinoma u matričnom obliku, pogodnom za obradu pomoću upravljačkog sistema.

Suština pristupa je korištenje iste vrste matematičkih izraza prilikom učitavanja početnih podataka, izračunavanje koeficijenata konačnih elemenata i globalne matrice krutosti sa vektorom opterećenja, dobijanje pseudo rješenja uz naknadnu obradu rezultata proračuna u obliku polinoma. U tu svrhu, oni su napisani u obliku RMP-a. Time se osigurava očuvanje ujednačenosti strukture specijalnog procesora (SP) i, kao rezultat, njegova proizvodnost u proizvodnji, troškovima itd. I u procesu rješenja, takav uređaj pruža ultra visoke performanse zbog paralelne obrade SSD-a, a također eliminira zastoje matričnog uređaja itd.

Da biste riješili ovaj problem potrebno je da uradite sljedeće:

1. Opišite test funkcije (spline) u obliku matrice i definirajte operacije na splajnovima predstavljenim u obliku RMP-a.

2. Razlikovati i integrirati polinome u matričnom ili vektorskom obliku.

3. Pomnožite i zbrojite gornje matrice i vektore prije ili nakon izvođenja operacija diferencijacije ili integracije.

4. Izvršite operacije prema paragrafima. 2, 3 analitički i numerički.

5. Izračunajte rezultirajuće izraze.

Zapisujemo polinome / (X) i /2 (X) u obliku RMP:

i proizvod polinoma

7=/(X)=/ (X) / (X)=Uo+Ui X1 + Y2 X2+^=

Ao bo +(a bo+a o b)+(a o b2 + ax ^ + ^2 b0)+...

V matrični oblik

(aob0) (a, bo + aob1) (aob1 + a1b1 + a1bo)--1 X0

Y = / (X) * [F 1] * [F 2 ] = (aolo) (a1lo + aol1)--- Xí- (15)

_ (aobo)--- ] X2

Glavni nedostatak matričnog predstavljanja i izvođenja operacija na njima kao što su množenje, sabiranje itd. u matričnom obliku je redundantnost kako u predstavljanju tako i u izvođenju procedura na njima. Dakle, kod množenja matrica Atm i Xmt potrebno je izvršiti m3 operacije, a za množenje matrice potrebno je

imaju t2 SU. Stoga, da bi se smanjila potrošnja opreme i smanjilo vrijeme potrebno za izvođenje operacija množenja, predlaže se korištenje vektorske reprezentacije polinoma X umjesto matrične. Ovo će smanjiti broj kontrolnih sistema za hiljadu puta i biće potrebne operacije

Komentar. Prikazana je mogućnost smanjenja broja operacija na m. Množenje matrica predstavljenih u obliku RMP-a se izvodi kao proizvod vektora iste dimenzije.

Procedura množenja vektora / (X) u upravljačkom sistemu (napisana pomoću RMP u matričnom obliku [F]) može se zamijeniti postupkom množenja matrice vektorom. Da bismo ga izveli kao operaciju množenja matrice vektorom u (15), potrebno je zamijeniti prikaz funkcije /X sa transponiranim /1 (X) (u obliku matrice [F1] do [F1]T ):

/T (X) *[F 1] T = a1 ao

i u (13) ga predstaviti u obliku /2(X") (u matričnom obliku [F 2 ]) kao vektor stupca:

Uvek predstavljajući prvi polinom (množenik) u obliku /1T (X), a drugi polinom (množenik) u obliku kolone /2*(X), definišemo proizvod dva polinoma u opštem obliku:

7=/(X) * /2 (X)-* /T (X) * Š=[F 1]t * [F 2 ]

i u matričnom obliku:

a0 b ■ (a0b0) >0"

g= aj a0 * b = (aA + a0b1) = g =[F *]* f *(X),

1 o Ö sT 2 a2 i A _ _(a2b0 + a1b1 + a0b2)1 _ g _

[ f:(X)]G =.

Izjava o problemu

U odnosu na jedan od MVN-ova – metod kolokacije – pokazaćemo mogućnost korištenja RMP-a opisanog gore.

Metoda kolokacije

Razmotrimo, koristeći primjer iz rješenja jednadžbe oblika

L(u) - p = d2 u / d x2 + u + x = 0 (20)

na intervalu 0< x < 1 с ГУ, и = 0 при x = 0, и = 0 при x = 1. (21)

Vrijednosti diferencijalna jednadžba su zadovoljni na nekoliko kolokacijskih tačaka.

Aproksimacija se bira u obliku izraza

i = x(1-x)(a1 + a2 x +...),

koji zadovoljava PG za bilo koje a..

Ostavljajući samo 2 člana u aproksimirajućoj jednadžbi (22), zapisujemo je koristeći RMP:

i = x(1-x)(a1 + a2 x)= a1(x-x2) + a2(x2 -x3)^ a

A1g + a2g. (23)

Da bismo dobili grešku, izračunavamo prvi izvod aproksimativne funkcije:

E i/E x = E (a1 x -a1 x 2 + a2 x 2 -a2 x3)E x = (a 1-2a1 x +2a2 x-3a2x2) =

A1(1 - 2 x)+ a2(2 x - 3x2) (24)

i drugi derivat

d 2 i / d x 2 = d (a j -2 a 1 x +2 a 2 x 2 -3 a2 x3) dx =

D (a1 - 2a1 x) dx + d (2a2x - 3a2x)dx =(-2 a j+2 a 2 x -6 a 2 x).

Nakon specificiranja aproksimirajuće funkcije (23) iz jednačine (10), utvrđujemo grešku e, koristeći njenu notaciju u obliku RMP:

e = b(u)-p = x + a1(-2+ x-x 2)+ a2(2-6x + x2-x3)^

1 o 0 0 1 "- 2 1 -10 " 1 -1 6 - 2 1

0 1 0 - 2 1 -1 2 - 6 1

b(u) - p = (-2 a 1 +2 a2 x -6 a2 x 2)+ a1(x - x2) + a2 (x2 - x3) + x =0. (27)

x = (2a1 - 2a2 + 6a2x) - (a1 (x - x2) + (a2 (x2 - x3) =

A1(2 - x + x 2) + a2(-2 + 6 x - x2 + x3). (27a)

Za odabrane kolokacijske tačke x 1 =1/4, x 2 =1/2 sastavlja se sistem jednačina

I (2 - x1 + x1)a1 (-2 + 6x1 - x1 + x1)a2 = 1/4,

[(2-x2 + x22)a1 (-2 + 6x2 -x22 + x^)a2 = 1/2.

Nakon izračunavanja vrijednosti koeficijenata za nepoznate a1 i a2 rješavanjem sistema

“29/16 - 35/64“ * b 1 =11/41 ili “0,8125 - 2,1875“

7/4 7/8 ¿ 2 11/2Í 1,75 0,875 _

Definirajmo vrijednosti ^=6/31(0,193548), i 2=40/217 (0,184332). Ovo će osigurati izračun iz (23) vrijednosti koje su nam potrebne i:

u = x (1-x)(a 1 + a 2 x)= a 1(x -x2)+ a 2 (x2- x 3)=(x (1-x)(6/31+40/217 x ).(30)

Za xi = 1,2,3 imamo

x 1=1/4, i 1=1/4* (1-1/4)* (6/31+40/217* 1/4)=0,0436,

x 2 =1/2, u2=1/2* (1-1/2)* (6/31+40/217* 1/2)=0,0703,

x 3 = 3/4, u3 = 3/4 * (1-3/4) * (6/31 + 40/217 * 3/4) = 0,0618.

Rješenje problema ćemo opisati u fazama.

Predstavljanje polinoma aproksimirajućih funkcija (22) u obliku

A1(x - x)+ a2(x - x)^ a1

0 1 -1 0 0 1 -1 01 0

0 0 1 -1 0 0 1 00 0

i operator [A] diferencijacije matrice u obliku

E / E x = [A] =

00200 0 0 0 3 0 00004

Izračunajmo:

Analitički, prvi izvod funkcije i iz (24):

E i/E x = E (a1 x- a1 x2 + a2 x2-a2 x3)/E x = (a1-2a1 x)+(2a2 x-3 a2 x2);

E i / E x = [ A ] * a 1

x1 Eh + [ A ] * a

x1 Eh + [ A ] * a x2

x1 Eh = a 1 „2

1 0 0 2 - 1 o 1 yu - 6 0 "

0 2 - x1 + a 2 2 -

1 - 2 1 x 2 2 1 2

i drugi izvod funkcije i (25) napisan u obliku RMP:

E 2 i / E x 2 = E / E x (-2 a1+2 a2 -6 a2 x)=

i 0 0 2 - i x0 1 0 6 - 2 1

[ A ] a 1 0 2 - x1 Ekh + [ A ] a2 2 - 6

x1 Eh+[A] a2

Izračunajmo grešku (e) pisanjem jednačine (26) u obliku RMP:

"0 1 0 0" "- 2 1 -1 0" "2 - 6 1 -1"

0 1 0 - 2 1 -1 i 1

0 1 1 - 2 1 2 2 - 6

Uz pretpostavku da je e = 0 za odabrane kolokacijske tačke x1=1/4, x2=1/2 iz jednadžbi.

x i +(-2+ x i -x 2)a 1+(2-6x i + x 2 -x 3)a2 = 0, (36)

x i =(2x i + x 2)a 1+(-2+6x i-x 2 + x 3)a 2, (36a)

stvaramo sistem. Predstavimo polinome na a1 i a2 u obliku cirkulanta (regularna matrična reprezentacija):

/ (x a1)= a 1(2- x i + x 2)^ a 1

A 1 * [ x x x x ] ^ / (x „),

I (x)= a 2 (-2+6 xi - x2+ x3)^ a

A 2 [-2 6-1 1] * [ x x x x ] ^ I (x).

Za odabrane kolokacijske točke jednadžbi sistema (28), vrijednosti funkcije /* (xa) u vektorskoj notaciji mogu se izračunati na sljedeći način:

za x2 = 1/2:

x = 1 x1 = 1/4 x2 = 1/16

A1 [(2-1 1] * [x 0 x; x 2]t = a1 (2-1/4+1/16)= a11.8125; (37)

a 1 * [ x 2=1 x 2=1/2 x 2=1/4]t = a 1(2*1-1*1/2+1*1/4)= a 17/4= a 11 .75;

a 2 [-2 6-1 1] * [ x 0=1 x 1=1/4 x 2=1/16 x 3 = 1/64]t = a 2(-2*1+6*1/4 -1*1/16+1*1/64)=

A 2 35/64=-a 2 0,5469;

za x2 =1/2:

a 2 [-2+6-11]* [x 2=1 x 2=1/2 x 2=1/4x 2=1/8]t = a 2 (-2*1+6*1/2- 1* 1/4+1*1/8)=

A 2 7/8 = a 2 0,875.

Tada se sistem jednadžbi (28) sa koeficijentima izračunatim u (35)-(39) za prethodno određene kolokacijske točke može numerički napisati na sljedeći način:

1,8125 0,5469 1,75 0,875

[a.1 = ] 0,25 I a I 10,50 i

i njegovo rješenje prema shemi isključenja

"1,8125 - 0,5469 0,25 "

0 2,542968 0,46875

b 22=1/ 2,542968=0,393241, b „=1/1,8125=0,5517

a2 = b 22 * ​​0,46875 = 0,1843,

a= b 11 * (0,25+0,1843 * 0,5469)=0,1935.

Na osnovu izračunatih vrednosti koeficijenata a1 i a2 za jednačinu (23), u varijanti pisanja jednačine (30), može se predstaviti u obliku regularnog matričnog prikaza:

u = a 1(x-x 2)+ a 2(x 2 -x 3)=

koji omogućava korištenje CS-a za izračunavanje vrijednosti koeficijenata za odabrane kolokacijske točke:

a (x 1-2)= a * T = a10,1875 (za x1=1/4), (43)

a (x 2 x 2) = a1 * T = a10,25 (za x2 = 1/2), a2 (x 2 x 3) = a2 * T = a20,0469 (za x1 = 1,4), (44)

a2(x 2 x 2)= a2* T = a20,1406 (za x2=1/2).

Nakon toga izračunavamo vrijednosti funkcije i:

u = a10,1875+ a2 0,0469=0,1935 * 0,1875+0,1843 * 0,0469=0,0449, (45)

u = a10,25+ a2 0,1406=0,1935 * 0,25+0,1843 * 0,1406=0,0742.

Za nova tačka izračunavaju se kolokacije x =3/4 (sa opcijama u proračunskom procesu):

u = a1 * T + a2 * T = a1(3/4-9/16)+ a2 (9/16-27/64)= =(a10.75-a10.5625)+(a2 0.5625-a20 .4219 )=0,0346+0,0259=0,0605. (46)

Metoda momenata

Metoda momenata, takođe uključena u grupu pod opštim imenom MVN, za dati sistem jednačina uključuje razmatranje tačkasti proizvod reziduali e na nekoj težinskoj funkciji w:

< e, w >= 0, i = 1,2,...,N, (47)

gdje su wi funkcije težine. Oni mogu biti bilo koji skup linearno nezavisnih funkcija,

na primjer, 1, x, x2, x3,... .

Ako je ispunjen uslov da momenti višeg reda nestanu

< е, х^ >= 0, i = 0,1, (48)

tada se ovaj postupak naziva metodom momenata.

Razmatra se primjer iz unosa (20)-(22):

L(u) - p = E2u / E x2 + u + x =0, u = x (1- x) a1 + x 2 (1- x) a2

a funkcija greške u njoj je ortogonalizirana u odnosu na 1 i x:

j e* 1 * jx =0, (49)

j e* x * yx =0 (49a)

sa zamjenom greške e u sistem (49), (49a)

e = a j (-2+ x - x 2)+ a 2 (2-6 x + x 2 - x 3)+ x, (50)

x1 dx + a2 [A] *

x1 dx + a 2 [A]:

A 1(-2x + x 2/2-x 3/3) |0 + a 2 (2x-6x 2/2+ x 3/3-x 4/4)|"0 + x 2/2 |"0 : = a 1 (-2+1/2 -1/3)+ a 2 (2-3+1/3-1 /4)+1 /2=

11/6 a, -11/12 a 2+1/2=0.

11/6 a 1+11/12 a 2 =1/2, gdje je [ A] integraciona matrica u RMP notaciji, jednaka

Komentar. Treba imati na umu da kada se integriraju funkcije (sa RMP notacijom) u obliku proizvoda matrice [A] sa vektorom stupaca I* (x), broj stupaca m matrice mora biti jednak broju redova m vektora, a dimenzija rezultujućeg vektora kolone mk treba da bude za jedan veći: tk = t +1.

Analogno (51) izračunavamo drugi (49a) integral:

| Ê* x * dx = | (x + a 1(-2+ x-x 2))dx +1 a 2 (2-6x + x2-x 3)dx =

= | (x 2) dx +1 a 1(-2 x + x 2- x 3) dx +1 a 2 (2 x -6 x 2+ x 3- x 4) dx =

X 3/3 |0 + a 1 (-2x 2/2+ x 3 /3-x 4/4) |0 + a 2(x 2-2x 3+1/4x 4-1/5 x 5) | 0 =

=[ A ] * t dx + a 1[ A ] * t dx + a 2[ A ] * t dx =

x2 + a -1 + a 2 x3

T |0 + a 1t |0 + a2 t |= =1/3+ a1(-1+1/3-1/4)+ a2 (1-2+1/4-1/5)=1/3 +a111/12- a219/20. (11/12 a1+19/20 a2=1/3).

Otuda sistem jednačina za a1 i a2:

"11/6 11/12" . I a-1 ili "1,8333 0,91667"

11/12 19/20 1a2 1.1/3Í 0.91667 0.95

Sistem (54) rješavamo metodom eliminacije:

1,8333 0,91667 0,5

0 0,9014 0,1526_

X11 =1/1,18333=0,54546, b22 =1/0,9014=1,1094, a2 =0,1695, a1=0,18796.

Dakle, od x (1- x)(a1 + a2 x) za odabrane kolokacijske tačke imamo 1 =0,25 * 0,75(0,18796+0,1695 * 0,25) = 0,04319, u2 = 0,5 * 0,5(0,18796+0,18796+0,18796+0,1695) )=0,06816, i3 =0,75 * 0,25(0,18796+0,1695 * 0,75)=0,0590 .

Iz onoga što je diskutovano, jasno je da se upotreba MVN-a, kolokacija i momenata dobro uklapa u opštu ideologiju paralelne implementacije procesa računanja na nivou obrade složenih struktura podataka u jednom tehnološkom toku. Ovo takođe pokazuje mogućnost implementacije metoda u posebnom procesoru izgrađenom na bazi procesorskih elemenata sa skalarnim multiplikatorom u jezgru, sa orijentacijom na rešavanje problema matematičke fizike.

Poređenje vrijednosti izračunatih predloženom metodom sa vrijednostima izračunatim tradicionalnom aproksimativnom metodom pokazuje njihovu bliskost.

Pisanje originalnih jednačina u obliku RMP-a omogućava vam da:

Podići nivo obrade informacija (uključujući izvođenje operacija kao što su množenje, diferencijacija, integracija polinoma) sa nivoa brojeva na nivo obrade složenih struktura podataka;

Paralelno s računskim procesom izvodeći operacije u PE pomoću skalarnih množitelja uključenih u njegovu strukturu, odnosno u paralelnom specijalnom procesoru na strukturi dizajniranoj za izračunavanje matrica krutosti konačnih elemenata (FE), a zatim globalnu matricu s vektorom opterećenja u vezi sa upotrebom MKE-a u rješavanju MF zadataka.

Implementacijom ovog pristupa proširit će se obim primjene paralelnih struktura procesorskih elemenata (PE) izgrađenih na bazi skalarnih množitelja, omogućit će se ujednačavanje procesa računanja, počevši od faze pripreme početnih podataka sa naknadnim rješenjem. globalne matrice krutosti, čime se organizira jedan tehnološki (računarski) tok pri rješavanju MF zadataka.

U zaključku, sa dubokom zahvalnošću želim da se setim V.M. Glushkova. Pokrenuo je rad na upotrebi metode konačnih elemenata, podržao razvoj novih numeričke metode i strukture za rješavanje problema matematičke fizike primjenom MKE i drugih numeričkih metoda. Viktor Mihajlovič je ovaj zadatak smatrao teškim, ali vrlo važnim.

Vjerujem da su inicijatori autorovog rada iz vidnog ugla identificirani u mojoj seriji članaka o korištenju MVN-a za rješavanje MF problema primjenom FEM-a uključuju J. Connor i C. Brebbia, koji su objavili knjigu neophodnu za rad matematičara i inženjeri. Gore predložene metode mogu se uspješno primijeniti pri rješavanju problema koje su opisali u svojoj knjizi o zajedničkom ulaganju ili vektorskim procesorima CUDA arhitekture serije Tesla od nVidia, na primjer, ili AMD-a kao dijela GPU - CPU (grafika i centralni klaster procesori) koji izvode vektorske operacije.

REFERENCE

1. Connor J. Metoda konačnih elemenata u mehanici fluida / J. Connor, K. Brebbia; lane sa engleskog - L.: Brodogradnja, 1979. - 264 str.

2. Jedinstveni tehnološki tok u organizaciji proračuna - način povećanja performansi paralelnih struktura na elementima procesora tipa transputer / Ledyankin Yu.Ya.

Kijev, 1989. - 20 str. - (Preprint / Akademija nauka Ukrajinske SSR, Institut za kibernetiku imena V.M. Glushkov; 89-57).

3. Ledyankin Yu.Ya. O pitanju transformacije i paralelnog unosa graničnih uslova pri rješavanju graničnih zadataka u jednoj računskoj niti / Yu.Ya. Ledyankin // Matematičke mašine i sistemi. - 2012. - br. 1. - Str. 28 - 35.

4. Adinec A. Grafički izazov za superračunare / A. Adinec, V. Voevodin // Otvoreni sistemi. - 2008. - br. 4. - Str. 35 - 41.

Katedra za fizičku hemiju SFU (RSU)

NUMERIČKE METODE I PROGRAMIRANJE

Materijali za nastavni kurs

Sistemi linearnih jednačina

Sistemi od n linearnih jednadžbi sa n nepoznatih x 1, x 2, ..., x n se općenito pišu na sljedeći način:

gdje su a ij i b i proizvoljne konstante. Broj n nepoznatih naziva se red sistema.

Rješenje jednadžbe je takav skup vrijednosti varijabli x 1, x 2,..., x n, koji istovremeno pretvara sve jednačine sistema u identitet.

Neophodan i dovoljno stanje postojanje i jedinstvenost rješenja sistema jednačina je linearnu nezavisnost jednačine. Ili, preciznije, nejednakost sa nulom determinante sastavljene od koeficijenata sistema jednačina:

Ekvivalentna (i vrlo zgodna!!!) notacija za sistem linearnih jednačina je matrična notacija

ili skraćeno ,

što se lako može provjeriti ako koristite pravila množenja matrice: element koji stoji na sjecištu i-tog retka i j-te kolone matrice rezultata je skalarni proizvod vektora i-tog reda prva matrica i vektor j-te kolone druge matrice.

Koeficijenti nepoznatih čine kvadratnu matricu veličine n x n, (A), varijable i slobodni članovi jednadžbi su vektori stupaca dužine n(X) i (B), respektivno.

Rješenje sistema jednačina je vektor (X *) koji ovu matričnu jednačinu pretvara u identitet.

Za rješavanje sistema linearnih jednačina koriste se egzaktne metode (direktne) u kojima je broj aritmetičkih operacija potrebnih za pronalaženje rješenja precizno određen redoslijedom sistema, te iterativne (približne) metode, u kojima se korak- po-korak, vrši se iterativno usavršavanje rješenja.

Blizina bilo kojeg vektora (X) i rješenju sistema jednačina može se procijeniti procjenom blizine vektora zaostalog, izračunatog na sljedeći način, nultom vektoru:

Da biste izrazili mjeru blizine u obliku broja, koristite neke norma vektor, na primjer, Euklidska norma ili dužina vektora u n-dimenzionalni prostor (druga definicija je kvadratni korijen skalarnog proizvoda vektora sa samim sobom):

Ponekad se koriste i druge vektorske norme: maksimalna norma (jednaka najvećoj komponenti vektora u apsolutnoj vrijednosti)

ili zbroj norme (jednak zbiru apsolutnih vrijednosti vektorskih komponenti)

Uslovljenost linearnih algebarskih sistema

Numeričko rješavanje sistema algebarskih jednačina često se rješava u okviru matematičko modeliranje zadatak. U ovom slučaju, i dimenzija problema i priroda matrica mogu se značajno promijeniti. Proračuni izvedeni sa određenom tačnošću također utiču na rezultat rješavanja linearnih sistema. Osim toga, sami sistemski koeficijenti - matrica (A) i slobodni termini - (B) mogu se prikazati sa određenom greškom.

Dajemo primjer:

Sistem jednačina

Ima, kao što je lako vidjeti zamjenom, jedinstveno rješenje x = 1, y = 1.

Pretpostavimo da je prilikom pripreme sistema za rješenje desna strana prve jednačine određena sa malom apsolutnom greškom od +0,01, odnosno da je desna strana prve jednačine uzeta jednakom 11,01 umjesto 11.

Jedino rješenje ovog sistema jednačina biće vektor x=11,01 y=0.

Kao što možete lako vidjeti, u ovom slučaju se ispostavlja da je greška u određivanju vrijednosti varijabli znatno veća od greške u koeficijentu. Zovu se problemi u kojima mala promjena početnih parametara dramatično utječe na rezultat.

loše uslovljena

Razmotrimo općenito sistem linearnih jednačina u kojem je vektor slobodnih termina (B) predstavljen sa određenom apsolutnom greškom (ΔB). Ako je vektor(X) je tačno rješenje jednačine sa "tačnim" vektorom) .

(IN , onda ako postoji greška na desnoj strani (ΔB), rješenje sistema jednadžbi će se razlikovati od (X) za određeni vektor (ΔX)

koji se može napisati na sljedeći način:

Otvorimo zagrade na desnoj strani

I uzmimo u obzir tačnu jednačinu

množeći obje strane jednakosti matricom inverznom matrici koeficijenata

Dobili smo

one. apsolutna greška (ΔX) izračunavanja vektora rješenja (X) jednaka je proizvodu matrice inverzne matrici koeficijenata sistema jednačina i vektora apsolutne greške (ΔB).

Ako pređemo sa matrica i vektora na odgovarajuće norme, nalazimo da će norma vektora (ΔX) biti manja ili jednaka umnošku normi inverzne matrice i norme vektora greške

Dakle, ako je norma inverzne matrice velika, tada apsolutna greška rješenja može biti znatno veća od apsolutne greške desnih strana jednadžbi sistema. Procijenimo kako će se oni međusobno povezati relativno

greška rješenja i relativna greška koeficijenata.

Da bismo to učinili, normaliziramo dvije ranije dobivene jednadžbe: broj (mjera) uslovljenosti matrice A. Od ove vrednosti zavisi stepen uticaja greške koeficijenata sistema jednačina na grešku dobijenog rešenja. Ako je ovaj broj mali, onda se relativna greška rješenja neće mnogo razlikovati od relativne greške koeficijenata. Što je veći broj uslova, veći je uticaj greške koeficijenta na grešku rešenja.

Slična analiza se može izvesti u slučaju greške u specificiranju matrice koeficijenata sistema (ΔA). I u ovom slučaju se javlja i broj uslovljavanja.

Za razmatrane numerički primjer

I

Ako uzmemo, na primjer, maksimalnu normu matrice,

, onda dobijamo

za matricu (A) norma je 1011, a za matricu inverznu (A) - (A) -1 – 1101. Dakle, broj uslova se ispostavlja da je veći od 1.000.000!

Direktne (tačne) metode

Gauss i Gauss-Jordan metoda

Algoritam rješenja je da se proširena matrica sistema jednačina svede na trouglasti oblik (Gaussova metoda) ili pseudodijagonalni oblik (Gauss-Jordanova metoda).

Cramer metoda

IN ovu metodu(ako determinanta koju čine koeficijenti sistema nije jednaka nuli), vrijednosti varijabli se određuju na sljedeći način

I = 1, 2, …, n

Ovdje nazivnik sadrži determinantu matrice koeficijenata sistema. U brojiocu – determinanta matrice dobijena iz matrice koeficijenata zamenom i kolonu u vektor kolone slobodnih članova sistema.

Za sistem napisan u opštem obliku :

Metoda inverzije matrice

Rješenje sistema jednadžbi napisanih u matričnom obliku lako je pronaći ako koristite definiciju inverzne matrice:

(A)(A) -1 = (A) -1 (A) = (1) ,

gdje je (1) jedinična dijagonalna matrica.

stvarno,

Pomnožimo obje strane jednačine na lijevoj strani inverznom matricom koeficijenata sistema (A)-1

Dakle, da bi se riješio sistem, potrebno je invertirati matricu koeficijenata sistema i pomnožiti rezultirajući rezultat sa vektorom stupaca slobodnih termina .

Uprkos jednostavnosti notacije, metoda ima dovoljnu računsku složenost, koja se sastoji u pronalaženju inverzne matrice .

Približne (iterativne) metode

Jednostavna metoda iteracije, Seidelova metoda

Ove metode se razmatraju na primjeru sistemi nelinearnih jednačina.

Minimalni rezidualni metod

Za rješavanje linearnih sistema jednačina možete koristiti različite metode za traženje ekstrema. Problem rješavanja sistema jednačina zamjenjuje se ekvivalentnim problemom nalaženja ekstremuma funkcije n varijable.