Šaknų paieška ir optimizavimas

Įvardykite klausimą ir dydžius

Originaliame algebriniame mokomajame modelyje tegu x yra skaliarinis ilgio parametras, apribotas intervalu 1 m ≤ x ≤ 2 m. Nustatykime modeliuojamą jėgos atsaką S(x) = κ x², kur κ = 1 N/m², ir siekiamą jėgą F_target = 2 N. Apibrėžkime nesąryšį F(x) = κ x² − F_target. Šaknis r tenkina F(r) = 0 N, todėl vienintelis teigiamas sprendinys čia yra r = √2 m. Tai nustatytas atsakas, o ne eksperimentiškai patvirtintas jėgos dėsnis.

Šaknis atsako į lygties keliamą klausimą: kuri leistina įvesties vertė paverčia nurodytą nesąryšį nuliu? Minimumo taškas atsako į verčių palyginimo klausimą: kuri leistina įvesties vertė duoda mažiausią tikslo funkcijos vertę? Įvestis ir išvestis gali reikšti skirtingus dydžius. Nežinomasis gali būti ilgis, net jei lygties nesąryšis yra jėga, o optimizavimo tikslo funkcija – energija.

Minimizuojant pačią F būtų atsakyta į kitą klausimą: mažiausia jos vertė šiame intervale yra −1 N, kai x = 1 m, o ne 0 N šaknies taške. Vietoj to galima apibrėžti neneigiamą tikslo funkciją, pavyzdžiui, F(x)², kurios matavimo vienetai yra N², tačiau tai būtina aiškiai nurodyti. Kintamasis, tikslo funkcija ir apribojimai kartu apibrėžia optimizavimo uždavinį.

Nustatykite tinkamą šaknį apgaubiantį intervalą

Jei realioji nesąryšio funkcija yra tolydi visame uždarame intervale [a, b], priešingi nenulinių jos reikšmių intervalo galuose ženklai garantuoja bent vieną šaknį tarp jų. Jei reikšmė intervalo gale lygi nuliui, tas galas jau yra šaknis ir jį galima nagrinėti atskirai. Tolydumas ir apibrėžtos reikšmės visame intervale yra būtinos prielaidos; vien reikšmių ženklai intervalo galuose jų neužtikrina.

Mūsų daugianaris F yra tolydus intervale [1 m, 2 m], o F(1 m) = −1 N ir F(2 m) = +2 N. Šiame intervale jis griežtai didėja: kai b > a ≥ 1 m, F(b) − F(a) = κ(b − a)(b + a) > 0 N. Todėl šaknį apgaubiančiame intervale yra tiksliai viena šaknis. Bendruoju atveju tolydi nesąryšio funkcija nebūtinai yra monotoniška, o vien ženklo pasikeitimo sąlyga neįrodo šaknies vienaties.

Vienodi reikšmių ženklai intervalo galuose neįrodo, kad šaknies nėra. Pateiktos nesąryšio funkcijos Q(x) = (1 N/m²)(x − 1 m)² reikšmės yra Q(0.5 m) = Q(1.5 m) = 0.25 N, tačiau Q(1 m) = 0 N. Priešingai, D(x) = (1 N m)/(x − 1.5 m) keičia ženklą tarp 1 m ir 2 m, tačiau yra neapibrėžta ties 1.5 m ir savo apibrėžimo srityje niekada nelygi nuliui. Nė vienas iš šių pavyzdžių neatitinka visų griežtų šaknį apgaubiančio intervalo su ženklo pasikeitimu sąlygų.

Dalykite intervalą pusiau išlaikydami šaknį

Imkite intervalo vidurio tašką q = (a + b)/2 ir apskaičiuokite F(q). Jei ši reikšmė lygi nuliui, grąžinkite šią šaknį. Kitu atveju palikite tą pusę, kurios galuose reikšmių ženklai tebėra priešingi. Mūsų didėjančio modelio atveju, kai nesąryšis teigiamas, vidurio tašku pakeiskite viršutinį intervalo galą, o kai neigiamas – apatinį. Šis veiksmas išlaiko žinomą šaknį intervale ir sumažina intervalo plotį perpus.

Lentelėje parodyti keturi atnaujinimai, pradedant nuo intervalo [1 m, 2 m]. Kiekvienas tikrinamas vidurio taškas priklauso intervalui, buvusiam prieš toje eilutėje pateiktą atnaujinimą. Paskutiniame stulpelyje pateiktas intervalas po šio atnaujinimo. Dešimtainiai įrašai čia yra tiksliai nustatytos racionaliosios reikšmės; lentelė yra aritmetinis pavyzdys, o ne teiginys apie slankiojo kablelio skaičiavimus kiekviename kompiuteryje.

Po ketvirtojo atnaujinimo paliktas šaknį apgaubiantis intervalas yra [1.375 m, 1.4375 m]. Jo vidurio taškas, 1.40625 m, yra mūsų stabdymo pavyzdyje grąžinamas artinys. Jis skiriasi nuo ketvirtojo tikrinto taško, 1.4375 m. Skaičiavimo eigos įraše aiškiai atskirkite tikrintą tašką, paliktą intervalą ir grąžintą artinį.

Sustokite pasiekę uždavinį atitinkančią paklaidos ribą

Jei paliktame intervale yra r, o grąžinamas artinys x̂ yra šio intervalo vidurio taškas, |x̂ − r| ≤ (b − a)/2. Pradinį w₀ pločio intervalą faktiškai padalijus pusiau n kartų, palikto intervalo plotis yra w₀/2ⁿ, o vidurio taško paklaidos riba – w₀/2ⁿ⁺¹. Tai yra paklaidos ribos, o ne nežinoma tiksli paklaida.

Šiame pavyzdyje pasirinkite leistinąją ilgio paklaidą ε_x = 0.04 m ir sustokite, kai palikto intervalo pusplotis neviršija ε_x. Po trijų atnaujinimų pusplotis yra 0.0625 m, todėl sąlyga netenkinama. Po keturių jis yra 0.03125 m, todėl sąlyga tenkinama. Grąžinkite x̂ = 1.40625 m kartu su jį apgaubiančiu intervalu ir |x̂ − r| ≤ 0.03125 m; nepateikite keturių atnaujinimų kaip įrodymo, kad gauta tiksli šaknis.

Leistinoji liekana išreiškiama jėgos vienetais ir atsako į kitą klausimą. Šiame modelyje F(x) = κ(x − r)(x + r). Kai ir x, ir r yra intervale [1 m, 2 m], κ(x + r) ≥ 2 N/m, todėl |x − r| ≤ |F(x)|/(2 N/m). Šis atskirai išvestas ryšys leidžia iš jėgos liekanos gauti ilgio paklaidos ribą. Jis priklauso nuo šio modelio ir srities; vien liekanos slenkstis bendruoju atveju negarantuoja koordinatės paklaidos ribos.

Taikykite liestinės žingsnį laikydamiesi jo sąlygų

Niutono metodas diferencijuojamą liekaną lokaliai pakeičia jos liestine ir randa šios tiesinės aproksimacijos nulį. Kai F′(x_k) yra apibrėžta ir nelygi nuliui, siūlomas atnaujinimas yra x_(k+1) = x_k − F(x_k)/F′(x_k). Dalmuo turi ilgio vienetus: N padalyta iš N/m.

Mūsų jėgos liekanai F′(x) = 2κx. Pradėjus nuo x₀ = 1.5 m, gaunama F(x₀) = 0.25 N ir F′(x₀) = 3 N/m. Pataisa yra (0.25 N)/(3 N/m) = (1/12)m, o x₁ = (17/12)m. Šis artinys yra nurodytame intervale, o jo liekana F(x₁) = (1/144)N. Todėl pagal anksčiau išvestą, šiam modeliui būdingą paklaidos ribą gauname |x₁ − r| ≤ (1/288)m < 0.004 m.

Šis sėkmingas pasirinktas žingsnis negarantuoja kiekvieno Niutono metodo taikymo sėkmės. Kai išvestinė lygi nuliui, parodytas dalmuo neapibrėžtas; siūlomas taškas gali nepatekti į modelio apibrėžimo sritį; netinkami pradiniai taškai ar lokalus funkcijos elgesys gali neleisti metodui konverguoti. Išlaikomas tinkamas šaknį gaubiantis intervalas gali padėti apsaugoti metodą: priimti apibrėžtą siūlomą tašką, esantį griežtai intervalo viduje, ir įvertinti jo nesąryšį, o kitu atveju patikrinti intervalo vidurio tašką; abiem atvejais išlaikyti intervalo galus, kuriuose funkcijos reikšmių ženklai priešingi, nebent randama tiksli šaknis. Tai aprašo patikrinamą taisyklę, bet neįrodo, kad čia neaprašyta realizacija visada bus sėkminga.

Nesąryšių ir mažų žingsnių interpretavimas

Nesąryšio dydis ir pokyčiai tarp iteracijų dažnai naudojami kaip stabdymo kriterijai. Kiekvieną jų reikia interpretuoti. Mažas pokytis rodo, kad paeiliui išsaugoti kandidatai yra arti vienas kito; vien tai nepatvirtina artumo šakniai. Skaičiavimas taip pat gali sustoti pasiekęs išteklių ribą arba nebegalėdamas atvaizduoti naujo taško, kuris skirtųsi nuo ankstesnio. Šią priežastį nurodykite atskirai nuo reikalaujamo matematinio kriterijaus tenkinimo.

Kad pamatytumėte, kodėl svarbus nesąryšio mastelis, įveskite naują nesąryšį G(x) = 0.001 F(x), kur koeficientas yra bedimensis. Jo šaknys yra lygiai tokios pačios kaip F. Kai x = 1.5 m, G(x) = 0.00025 N, taigi tenkinama nustatyta 0.001 N nesąryšio riba. Tačiau šaknis yra mažesnė už 1.4375 m, todėl šio kandidato ilgio paklaida viršija 0.0625 m ir negali tenkinti ε_x = 0.04 m. Pakeitus lygties mastelį, jos nesąryšis sumažėjo, nors nei šaknis, nei kandidatas nepasikeitė.

Išsaugokite funkcijos versiją, leistiną intervalą, vienetus, funkcijos reikšmių ženklus intervalo galuose, atnaujinimus, grąžintą tašką, nesąryšį, stabdymo taisyklę ir tikrąją sustojimo priežastį. Jei modelio reikšmės apskaičiuojamos su triukšmu arba apytiksliai, apskaičiuoti jų ženklai gali būti nepatikimi. Tiksliai šaknį gaubiančio intervalo garantijai reikia patikimų ženklų ir nurodytų tolydumo sąlygų; prieš taikant šią garantiją tokiems skaičiavimams, reikia papildomo paklaidos arba neapibrėžties modelio.

Atskiros energijos tikslo funkcijos minimizavimas

Dabar įveskite atskirą mūsų sukurtą tikslo funkciją E(x) = E₀ + c(x − d)², kur x yra ilgis, E₀ = 1 J, c = 2 J/m² ir d = 3 m. Iš pradžių leiskite 0 m ≤ x ≤ 4 m. Leistina x reikšmė tenkina šį apribojimą, o globaliajame minimumo taške tikslo funkcijos reikšmė yra ne didesnė nei ties bet kuria kita leistina x reikšme. Lokaliajame minimumo taške taip lyginama tik su artimomis leistinomis x reikšmėmis.

Kvadratas yra neneigiamas, todėl E(x) ≥ 1 J, o lygybė galioja tik kai x = 3 m. Taigi x_min = 3 m yra vienintelis globalusis minimumo taškas intervale [0 m, 4 m], o E_min = 1 J yra mažiausia reikšmė. Išvestinė E′(x) = 2c(x − d) šiame taške lygi nuliui. Šiame modelyje energija niekada nepasiekia 0 J: radus minimumą, E šaknis nebuvo rasta.

Pakeiskite tik leistiną intervalą į [0 m, 2 m]. Taškas 3 m dabar yra neleistinas. Kiekvienam leistinam x galioja d − x ≥ 1 m, todėl E(x) ≥ 3 J, o lygybė galioja tik kai x = 2 m. Minimumas su apribojimu yra srities krašte, kur E′(2 m) = −4 J/m, o ne nulis. Tikslo funkciją ir leistiną sritį reikia nagrinėti kartu; išvestinės šaknis už šios srities ribų nėra leistinas atsakymas.

Teiginio apie optimumą patikra

Diferencijuojamai funkcijai vidiniame lokaliojo minimumo taške nulinė pirmoji išvestinė yra būtina sąlyga, o ne bendras minimumo įrodymas. Jei jos išvestinė būtų teigiama arba neigiama, pasislinkus pakankamai mažu atstumu viena iš dviejų leistinų krypčių, funkcijos reikšmė sumažėtų. Srities krašto taškus reikia tikrinti kitaip, nes abi kryptys nebūtinai yra leistinos. Iškilosios tikslo funkcijos grafikas tarp dviejų argumento reikšmių yra ne aukščiau už tiesės atkarpą, jungiančią atitinkamus grafiko taškus; iškilioji leistinoji aibė apima atkarpą tarp bet kurių dviejų savo taškų. Stipresniems diferencijuojamų funkcijų optimalumo kriterijams būtina nurodyta iškilumo struktūra ir sąlygos.

Mūsų energijos atveju argumentai, paremti kvadratu ir apibrėžimo sritimi, tiesiogiai įrodo globaliuosius minimumus; vien trumpas pasirinktose vietose apskaičiuotų reikšmių sąrašas to neįrodytų ištisiniame intervale. Priešingai, pateiktos funkcijos H(x) = 1 J − (1 J/m²)(x − 1 m)² intervale [0 m, 2 m] išvestinė tenkina H′(1 m) = 0 J/m, tačiau H(1 m) = 1 J yra didesnė už H(0 m) = H(2 m) = 0 J. Išsprendus jos išvestinės lygtį, nustatomas maksimumas, o ne minimumas.

Skaitinio optimizavimo ataskaitoje turėtų būti nurodyta tikslo funkcija, kintamieji ir vienetai, leistinosios srities apribojimai, pasirinktas metodas, pradinės sąlygos, stabdymo priežastis ir įrodymai, pagrindžiantys bet kokį teiginį apie lokalųjį ar globalųjį optimalumą. Nei mažas šaknies nesąryšis, nei pranešimas apie optimizavimo pabaigą neįrodo, kad algebrinis modelis aprašo realų įrenginį. Šie tikslūs pavyzdžiai moko, kaip patikrinti suformuluotą uždavinį; modelio fizikiniam tinkamumui ir jo reikšmių skaičiavimams su neapibrėžtimi pagrįsti reikia atskirų įrodymų.

Išnagrinėti pavyzdžiai

Pabandykite patys

1. Duota F(x) = (1 N/m²)x² − 2 N intervale [1 m, 2 m]. Raskite šaknį ir x vertę, ties kuria pati F yra minimali. Nurodykite abiejų x verčių ir minimalios nevykio vertės matavimo vienetus.

   Rodyti atsakymą ir paaiškinimą

   Šaknis yra √2 m. Pati F yra minimali ties 1 m, kur jos vertė yra −1 N. Abi x vertės yra ilgiai, o minimali nevykio vertė yra jėga.

   F griežtai didėja leistinajame intervale. Todėl jos nulis ir mažiausia reikšmė, atsižvelgiant į ženklą, pasiekiami esant skirtingoms parametro reikšmėms. Tikslo funkcija, tokia kaip F², reikštų atskirai apibrėžtą uždavinį.

2. Funkcijos D(x) = (1 N m)/(x − 1.5 m) reikšmės taškuose 1 m ir 2 m yra −2 N ir +2 N. Ar šis ženklo pasikeitimas garantuoja, kad tarp jų yra šaknis? Ar funkcijos Q(x) = (1 N/m²)(x − 1 m)² vienodos teigiamos reikšmės intervalo [0.5 m, 1.5 m] galuose garantuoja, kad šaknies nėra?

   Rodyti atsakymą ir paaiškinimą

   Nei viena, nei kita išvada neplaukia. D neapibrėžta taške 1.5 m ir savo apibrėžimo srityje neturi nulio. Q turi šaknį taške 1 m, nors jos reikšmės intervalo galuose yra vienodos ir teigiamos.

   Šaknį gaubiančio intervalo argumentas, grindžiamas tarpinių reikšmių teorema, reikalauja, kad funkcija būtų apibrėžta ir tolydi visame intervale. Esant šiai prielaidai, priešingų ženklų sąlyga garantuoja šaknies egzistavimą; ji nėra būtina kiekvienos šaknies sąlyga.

3. Pradėdami nuo išsaugoto F šaknį gaubiančio intervalo [1.375 m, 1.4375 m], atlikite dar vieną dalijimo pusiau metodo žingsnį. Pateikite naujojo intervalo vidurio tašką ir nustatykite, ar jo paklaidos riba tenkina ε_x = 0.02 m.

   Rodyti atsakymą ir paaiškinimą

   Tikrinamas taškas yra 1.40625 m, o liekana jame neigiama. Išsaugokite intervalą [1.40625 m, 1.4375 m], pateikite 1.421875 m ir nurodykite 0.015625 m paklaidos ribą, kuri tenkina tikslą.

   F(1.40625 m) = −(23/1024)N. Naujojo intervalo ilgis yra 0.03125 m, todėl jo vidurio taškas yra (1.40625 + 1.4375)m/2 = 1.421875 m, o pusė jo ilgio yra 0.015625 m. Pateikiamas taškas skiriasi nuo ką tik patikrinto taško.

4. Tarkime, G(x) = 0.001 F(x), koeficientas yra bedimensis, o jėgos modelis ir apibrėžimo sritis lieka tie patys. Ar taške x = 1.5 m sąlygos |G(x)| ≤ 0.001 N tenkinimas garantuoja, kad |x − r| ≤ 0.04 m? Paaiškinkite remdamiesi anksčiau išsaugotu šaknį gaubiančiu intervalu.

   Rodyti atsakymą ir paaiškinimą

   Ne. G(1.5 m) = 0.00025 N tenkina liekanos kriterijų, tačiau iš r < 1.4375 m išplaukia, kad 1.5 m − r > 0.0625 m, taigi viršijama 0.04 m riba.

   Dauginimas iš nenulinės konstantos nekeičia nulių ir fizikinių vienetų, tačiau pakeičia liekanos dydį. Nustatant atitinkamą koordinatės paklaidos ribą, būtina atsižvelgti į naująjį liekanos mastelį; vien perkėlus senąją jėgos slenkstinę reikšmę, ši riba nenustatoma.

5. Tai pačiai F pasiūlykite vieną Niutono metodo žingsnį iš x₀ = 2 m. Pateikite išvestinę, pataisą, kandidatinį tašką ir liekaną jame. Ar šis vienas skaičiavimas įrodo konvergavimą iš kiekvieno leistino pradinio taško?

   Rodyti atsakymą ir paaiškinimą

   F′(2 m) = 4 N/m, pataisa yra 0.5 m, kandidatinis taškas yra 1.5 m, o liekana jame yra 0.25 N. Šis vienas žingsnis neįrodo bendrojo teiginio apie konvergavimą.

   F(2 m) = 2 N, todėl padaliję iš 4 N/m gauname 0.5 m, o atėmę šią vertę iš 2 m gauname 1.5 m. Pasirinktas kandidatas yra leistinas, tačiau kiekvienam bendresniam teiginiui apie konvergavimą reikia savų sąlygų ir pagrindimo.

6. Atskirai pateiktos funkcijos H(x) = 1 J − (1 J/m²)(x − 1 m)² intervale [0 m, 2 m] išvestinė lygi nuliui taške 1 m. Ar šiame taške pasiekiamas minimumas? Nurodykite mažiausią vertę ir visas x vertes, kurioms ji pasiekiama.

   Rodyti atsakymą ir paaiškinimą

   Stacionariajame taške 1 m pasiekiamas maksimumas, kurio vertė yra 1 J. Mažiausia vertė yra 0 J; ji pasiekiama tiek taške 0 m, tiek taške 2 m.

   Šiame intervale (x − 1 m)² vertės yra tarp 0 m² ir 1 m². Atimant šį dydį, padaugintą iš teigiamo koeficiento, verčių tvarka apsiverčia: energija didžiausia intervalo viduryje ir mažiausia abiejuose jo galuose. Vien išvestinės šaknies nepakanka ekstremumo tipui nustatyti.

Ką verta įsidėmėti

• Prieš pasirinkdami metodą, nurodykite lygtį arba tikslo funkciją, leistinas įvesties vertes ir dydžių matavimo vienetus.
• Intervalas, kurio galuose tolydi funkcija yra priešingų ženklų, užtikrina bent vienos šaknies egzistavimą; vienaties įrodymui reikia papildomo pagrindimo.
• Grąžinkite ir užrašykite išsaugoto intervalo vidurio tašką kartu su paklaidos riba, lygia pusei intervalo pločio, ir aiškiai nurodykite iteracijų indeksavimą.
• Liekanos dydis, koordinatės paklaida ir mažas iteracijos žingsnis matuoja skirtingus dalykus; juos siekite tik patikrinę tam būtinas sąlygas.
• Niutono metodo žingsniui reikia apibrėžtos, nelygios nuliui išvestinės ir apibrėžimo srities patikros; sėkmingas pavyzdys nėra universalus konvergavimo rezultatas.
• Optimizavimo išvados priklauso nuo leistinosios srities, o vien stacionarusis taškas ar pranešimas apie skaičiavimo pabaigą neįrodo nei globalaus minimumo, nei modelio fizikinio pagrįstumo.