Acasă | Despre noi | feedback-ul
Un grup extins de metode de rafinare a rădăcinilor este reprezentat de metode iterative - metode de aproximare succesivă. Aici, spre deosebire de metoda dihotomiei, nu este dată intervalul inițial al locației rădăcinii, ci aproximația sa inițială este dată.
Cea mai populară dintre metodele iterative este metoda lui Newton (metoda tangentelor).
Fig. 3. Metoda tangentelor
Să se cunoască o valoare aproximativă Zn a rădăcină X *. Aplicând formula Taylor și restricționând-o la doi termeni, avem
Din punct de vedere geometric, această metodă propune construirea unei tangente la curba y = f (x) la punctul ales x = Zn. găsiți punctul de intersecție cu abscisa și luați acest punct pentru următoarea aproximare cu rădăcina (3).
Fig. 6 Interpretarea geometrică a metodei simple de iterație
De aici poate fi construit un proces iterativ
Luați, de exemplu ecuația x 3 + x -1000 = 0. Este evident că rădăcina ecuației oarecum mai mic de 10. Dacă vom rescrie ecuația în forma x = 1000 - x 3 și începe procesul iterativ când x0 = 10. apoi de la primele aproximări divergența sa este evidentă. Dacă luăm în considerare f '(x) = 3x 2 + 1> 0 și luată ca valoare maximă aproximativă f' (x) M = 300. atunci putem construi un proces iterativ convergentă bazat pe reprezentarea
Este posibilă selectarea artificială a formei corespunzătoare a ecuației, de exemplu:
Considerăm problema găsirii rădăcinii ecuației prin metoda Newton folosind referințe ciclice. Luați, de exemplu, ecuația patratică: x 2 - 5x + 6 = 0. a cărui reprezentare grafică este dată pe 7 Găsiți rădăcina acestei ecuații (și orice altă), folosind o singură celulă Excel.
Pentru a activa modul de calcul ciclic, în fila Instrumente / Opțiuni / Calcule, activați caseta de validare Iterație. dacă este necesar, modificați numărul de repetări ale ciclului în câmp Numărul de limite de iterații și precizia calculelor în câmpul de eroare relativă (în mod implicit, valorile lor sunt 100 și respectiv 0,0001). În plus față de aceste setări, alegeți opțiunea de efectuare a calculelor: automat sau manual. Cu un calcul automat, Excel scoate imediat rezultatul final, cu calcule efectuate manual. puteți vedea rezultatul fiecărei iterații.
Fig. 7. Graficul funcțiilor
Alegem o celulă arbitrară, îi atribuim un nume nou, să zicem - X. și introducem o formulă de recurență care specifică calculele prin metoda Newton:
unde F și F1 definesc expresiile pentru calcularea valorilor funcției și, respectiv, derivatului acesteia. Pentru ecuația noastră patratică, după introducerea formulei în celulă, apare o valoare de 2 corespunzând uneia dintre rădăcinile ecuației (Figura 8). În cazul nostru, aproximarea inițială nu a fost specificată, procesul de calcul iterativ a început cu valoarea implicită stocată în celula X și egală cu zero. Și cum să obțineți a doua rădăcină? De obicei, acest lucru se poate face prin modificarea aproximării inițiale. Problema setării setărilor inițiale în fiecare caz poate fi rezolvată în moduri diferite. Vom demonstra o tehnică bazată pe utilizarea funcției IF. Pentru a crește vizibilitatea calculelor, celulele au primit denumiri semnificative (figura 8).
· În celula Khnach (B4) introducem aproximația inițială - 5.
· În celula Htekushch (C4) scriem formula:
= IF (Htekusch = 0; Hnach; Htekusch- (Htekusch Htekusch ^ * + 2-5 6) / (2 * Htekusch-5)).
· În celula D4 se introduce formula care specifică calculul valorii funcției în punctul Xecouc. care vă va permite să monitorizați procesul decizional.
· Rețineți că în prima etapă a calculelor, valoarea inițială va fi plasată în celula Xekushk și apoi numărul va începe cu formula în etapele ulterioare.
· Pentru a modifica aproximația inițială, nu este suficient să modificați conținutul celulei Hnach și să începeți procesul de calcul. În acest caz, calculele vor continua, începând cu ultimul calcul
Fig. 8. Determinarea setărilor inițiale
valori. Pentru a zero valoarea stocată în celula Htekushch. trebuie să rescrieți formulele de acolo. Pentru aceasta, selectați celula care conține formula făcând dublu clic pe ea (conținutul celulei va fi afișat în bara de formule). Dacă faceți clic pe butonul (apăsând tasta) Enter, începeți calcularea cu o nouă aproximație inițială.
• În celula C3 (Figura 10), introducem o formulă pentru calcularea valorii funcției în ecuația din stânga semnului egal. Ca argument, folosim referința la celula C2, adică = C2 <2-5 * C2 + 6.
• In fereastra de dialog Selectarea parametrului (. Figura 10) în celula Set, introduceți referința celulei formulei din valoarea - rezultatul așteptat în valoarea schimbare a celulei - referința celulei, care va stoca ajustarea valorii parametrilor (conținutul acestui celula nu poate fi o formulă).
• După ce faceți clic pe buton, Ok Excel afișează dialogul Rezultatul selecției parametrilor. Dacă valoarea selectată trebuie salvată, atunci
Să revenim la exemplul respectiv. Din nou, se pune întrebarea: cum să obțineți a doua rădăcină? Ca și în cazul precedent, este necesar să se precizeze aproximarea inițială. Acest lucru se poate face după cum urmează (figura 11, a):
Fig. 11. Găsirea celei de-a doua rădăcini
• În celula X (C2) introducem aproximația inițială.
• În celula Xi (C3) introducem o formulă pentru calcularea următoarei aproximări la rădăcină, adică = X- (X ^ 2-5 * X + 6) / (2xX-5).
• În celula C4 vom pune o formulă care specifică calculul valorii funcției pe partea stângă a ecuației inițiale în punctul Xi.
• Apoi selectați comanda de selectare a parametrilor, unde acceptăm celula C2 ca celula variabilă. Rezultatul calculelor este prezentat în Fig. 11, b (în celula C2 - valoarea finală, iar în celula C3 cea precedentă). Totuși, toate acestea se pot face și ceva mai simplu. Pentru a găsi a doua rădăcină, este suficient să plasăm constanta 5 în celula C2 ca aproximație inițială (Figura 10) și apoi să începem procesul de Selectare a unui parametru.
Comanda de selectare a parametrilor este convenabilă pentru rezolvarea problemelor de găsire a unei valori țintă specifice, în funcție de un parametru necunoscut. Pentru sarcini mai complexe, utilizați comanda Find Solution (Solver). Probleme care pot fi rezolvate cu ajutorul Solution Search. în formula generală sunt formulați după cum urmează:
Variabilele necesare - celulele foii de lucru Excel - se numesc celule reglabile. Funcția obiectiv este F (x1, x2, ..., xn). uneori numită pur și simplu un scop, ar trebui să fie dat ca o formulă în celula foii de lucru. Această formulă poate conține funcții definite de utilizator și trebuie să depindă (se referă la) celulele controlate. În momentul în care problema este setată, se determină ce să faceți cu funcția obiectivă. Puteți alege una dintre următoarele opțiuni:
Funcțiile G (x1, x2, ..., xn) se numesc constrângeri. Acestea pot fi specificate atât sub forma egalității, cât și a inegalităților. Pe celulele ajustabile, puteți impune restricții suplimentare: non-negativitate și / sau întreg, atunci soluția căutată este căutată în regiunea pozitiv și / sau întreg.
Această formulă include cea mai largă gamă de probleme de optimizare, inclusiv soluția unor ecuații și sisteme de ecuații, probleme de programare liniară și neliniară. Este de obicei mai ușor să formulați astfel de probleme decât să le rezolvați. Apoi, pentru a rezolva o problemă de optimizare specifică, este necesară o metodă special concepută. Solverul are în arsenalul său instrumente puternice pentru rezolvarea unor probleme similare: metoda gradientului generalizat, metoda simplex, ramura și metoda limită.
Luați în considerare modul de utilizare a Căutării unei soluții utilizând exemplul aceleiași ecuații patrate.
Fig. 11. Caseta de dialog Find Solution
După deschiderea dialogului Find Solution (11), trebuie să efectuați următoarele acțiuni:
2. Pentru a maximiza valoarea celulei țintă, setați comutatorul la valoarea maximă din poziție # 61496; comutatorul minim este utilizat pentru ao minimiza. în cazul nostru, setați comutatorul în poziția valorii și introduceți valoarea 0;
4. În câmpul Restricții, utilizați butonul Adăugați pentru a introduce toate restricțiile pe care trebuie să le corespundă rezultatul căutării: pentru exemplul nostru, nu este necesar să setați limite;
5. Pentru a începe procesul de căutare a soluției, faceți clic pe butonul Executare.
Pentru a salva soluția rezultată, trebuie să utilizați butonul Salvați soluția găsită în caseta de dialog Căutați soluția care apare. După aceea, foaia de lucru va lua forma prezentată în Fig. Soluția obținută depinde de alegerea aproximării inițiale, care este dată în celula C4 (argumentul funcției). Dacă introducem o valoare de 1,0 ca aproximație inițială în celula C4. apoi cu ajutorul căutării soluției găsim a doua rădăcină egală cu 2,0.
Fig. 12. Rezultatele căutării
Opțiuni care controlează activitatea Solution Search. Parametrii specificați în fereastra Parametri (fereastra apare dacă faceți clic pe butonul Opțiuni din fereastra Căutare soluție), următoarele (Figura 13):
Fig. 13. Configurarea Solver
· Timpul maxim - limita timpul alocat pentru procesul de a găsi soluții (implicit este setat la 100 de secunde, ceea ce este suficient pentru sarcinile care sunt de aproximativ 10 de restricții, în cazul în care problema de dimensiuni mari, în timp ce nevoia de a crește).
· Limitarea numărului de iterații - este un alt mod de a găsi o limită de timp prin stabilirea numărului maxim de iterații. Valoarea implicită este de 100, și, cel mai adesea, în cazul în care decizia nu este primit pentru 100 de iterații, apoi cu o creștere a numărului acestora (în domeniu, puteți introduce un timp care nu depășește 32767 de secunde), probabilitatea de a obține rezultatul este mic. Este mai bine să încercați să modificați aproximația inițială și să porniți din nou procesul de căutare.
· Eroare relativă - specifică precizia cu care este determinată corespondența celulei cu valoarea țintă sau aproximarea cu constrângerile specificate (fracțiunea zecimală de la 0 la 1).
· Toleranță - specificată în% numai pentru sarcini cu constrângeri întregi. Găsirea unei soluții pentru astfel de probleme, în primul rând găsește soluția optimă non-număr întreg, și apoi încearcă să găsească cel mai apropiat punct întreg, o decizie care ar fi diferit de cel optim nu este mai mult decât o anumită sumă de interes în acest parametru.
· Convergență - valoarea relativă schimbare atunci când celula țintă în ultimele cinci iterații devine mai puțin decât numărul (fracțiunea de intervalul 0 - 1), specificate în acest parametru, căutarea se oprește.
· Model liniar - această casetă de selectare trebuie activată atunci când funcția obiectivă și constrângerile sunt funcții liniare. Acest lucru accelerează procesul de găsire a unei soluții.
· Valori non-negative - acest steag vă permite să setați constrângeri asupra variabilelor, ceea ce vă va permite să căutați soluții în intervalul pozitiv de valori fără a specifica restricții speciale la limita inferioară a acestora.
· Scalare automată - această casetă de selectare ar trebui activată când scala valorilor variabilelor de intrare și funcția obiectivă și constrângerile diferă, probabil, de ordinele de mărime. De exemplu, variabilele sunt specificate în bucăți, iar funcția obiectivă care determină profitul maxim este măsurată în miliarde de ruble.
· Afișați rezultatele iterațiilor - această casetă de selectare vă permite să activați un proces de căutare pas cu pas, afișând rezultatele fiecărei iterații pe ecran.
· Estimări - acest grup servește pentru a indica metoda de extrapolare - liniară sau patratică - pentru a obține estimări inițiale ale valorilor variabilelor în fiecare căutare unidimensională. Linear servește la utilizarea extrapolării liniare de-a lungul vectorului tangent. Quadratic servește la utilizarea extrapolării patrate, care dă rezultate mai bune în rezolvarea problemelor neliniare.
· Diferențe (derivate) - acest grup servește pentru a indica metoda diferențierii numerice, care este utilizată pentru a calcula derivatele parțiale ale funcțiilor țintă și limitative. Parametrul Direct este utilizat în majoritatea sarcinilor, unde rata de schimbare a constrângerilor este relativ scăzută. Parametrul Central este utilizat pentru funcțiile care au un derivat discontinuu. Această metodă necesită mai multe calcule, însă aplicarea acesteia poate fi justificată dacă se emite un mesaj care nu permite obținerea unei soluții mai exacte.
· Metoda de căutare - este utilizată pentru a selecta algoritmul de optimizare. Metoda Newton a fost considerată mai devreme. Metoda gradientului conjugat necesită mai puțină memorie, dar sunt efectuate mai multe iterații decât în metoda Newton. Această metodă ar trebui utilizată dacă sarcina este suficient de mare și este necesară economisirea memoriei și dacă iterațiile dau prea puțină diferență în aproximările succesive.
Puteți salva modelul de căutare a soluției în următoarele moduri:
1. Când salvați registrul de lucru Excel după găsirea soluției, toate valorile introduse în casetele de dialog Find Solution. sunt salvate împreună cu datele din foaia de lucru. Cu fiecare foaie de lucru din registrul de lucru, puteți salva un set de valori pentru parametrii Search Solution;
2. În cazul în care într-o foaie de lucru Excel trebuie să ia în considerare mai multe modele de optimizare (de exemplu, pentru a găsi valoarea maximă a mai multor funcții maxime și minime a unei funcții, sau), este mai convenabil să păstreze aceste modele folosind butonul Options / Salvare model de căutare de soluții pentru ferestre. Intervalul pentru modelul stocat furnizează informații cu privire la celula țintă, de celule variabile, pe fiecare dintre restricțiile și toate valorile din dialog Opțiuni. Modelul de selecție pentru o anumită problemă de optimizare utilizând setările butonul Load Model de căutare soluții / dialog;
3. Un alt mod de a salva parametrii de căutare este să le salvați ca script-uri numite. Pentru a face acest lucru, faceți clic pe butonul Salvați scriptul din caseta de dialog Căutarea rezultatelor soluției.
În plus față de introducerea valorilor optime în celule mutabile, căutarea de soluții vă permite să prezentați rezultatele sub forma a trei rapoarte: Rezultate. Stabilitate și limite. Pentru a genera unul sau mai multe rapoarte, trebuie să le selectați numele în caseta de dialog Soluție soluție soluție. Să analizăm în detaliu fiecare dintre ele.
Fig. 14. Raportul privind durabilitatea
Raportul privind durabilitatea (14) conține informații despre cât de mult este celula țintă sensibilă la schimbările în constrângeri și variabile. Acest raport are două secțiuni: unul pentru celulele mutabile și celălalt pentru constrângeri. Coloana din dreapta din fiecare secțiune conține informații despre sensibilitate. Fiecare celulă variabilă și constrângerile sunt listate pe o linie separată. Secțiunea pentru celulele mutabile conține valoarea gradientului normalizat, care arată modul în care întreaga celulă reacționează la o creștere a valorii în celula variabilă corespunzătoare cu o unitate. În mod similar, multiplicatorul Lagrange din secțiunea de constrângere arată modul în care celula țintă reacționează la o creștere a valorii limită corespunzătoare cu o unitate. Când se utilizează constrângeri întregi, Excel afișează rapoartele și limitele de sustenabilitate care nu se aplică sarcinilor cu constrângeri întregi. Dacă caseta de selectare Mod Linear este selectată în caseta de dialog Opțiuni căutare soluție. raportul de sustenabilitate conține mai multe coloane suplimentare de informații.
Fig. 15. Raport privind rezultatele
Raport privind rezultatele (15) conține trei tabele: prima arată informația despre funcția țintă înainte de calcul, al doilea - valorile variabilelor necunoscute, soluția rezultată a problemei, în a treia - rezultatele soluției optime pentru restricțiile. Acest raport include, de asemenea, informații privind parametrii pentru fiecare restricție, starea și diferența. Starea poate lua trei stări: conectate, independente sau nerealizate. Semnificația diferenței - diferența dintre valoarea în limitele scoasă la ieșire de celule în obținerea de soluții și numărul stabilit în partea dreaptă a formulei limită. Restricții conexe - restricția pentru care valoarea diferența este zero. limitare nelegat - această restricție, care a fost efectuată cu o diferență de zero.
Articole similare
Trimiteți-le prietenilor: