Dull Iteriad wrth Ddod o Hyd i Wreiddiau
Mewn mathemateg gymhwysol, ffiseg, peirianneg a chyfrifiadureg, mae problem "dod o hyd i wreiddyn" yn codi'n aml iawn. Gwreiddyn yw gwerth \(x\) sy'n gwneud ffwythiant yn sero, hynny yw, yr ateb i'r hafaliad:
\[
f(x)=0
\]
Nid oes gan bob hafaliad atebion y gellir eu mynegi mewn fformiwlâu ffurf gaeedig, fel hafaliadau cwadratig. Ar gyfer llawer o achosion yn y byd go iawn—fel hafaliadau cymhleth anlinellol—mae angen dulliau rhifiadol arnom. Un o'r dulliau pwysicaf yw'r dull iterus, gweithdrefn sy'n cynhyrchu cyfres o atebion bras sy'n dod yn agosach at y gwreiddyn trwy iteriad.
Mae'r erthygl hon yn trafod cysyniadau sylfaenol dulliau iterus, eu hamodau cydgyfeirio, a rhai dulliau iterus a ddefnyddir yn gyffredin ar gyfer dod o hyd i wreiddiau.
-
1. Syniad Sylfaenol y Dull Iteriad
Mae'r dull iteriad yn gweithio trwy wneud dyfaliad cychwynnol \(x_0\), yna ei wella'n raddol i gael y dilyniant:
\[
x_0, x_1, x_2, \dotiau, x_n
\]
gyda disgwyliadau:
\[
x_n \to \alpha
\]
lle mae \(\alpha\) yn wreiddyn gwir yr hafaliad \(f(x)=0\).
Yn gyffredinol, mae'r dull iteriad yn trawsnewid y broblem \(f(x)=0\) i ffurf gyfwerth:
\[
x = g(x)
\]
Yna perfformir iteriad:
\[
x_{n+1} = g(x_n)
\]
Os yw'r broses hon yn cydgyfeirio, yna mae pwynt sefydlog \(g(x)\) yn ddatrysiad gwreiddyn i'r hafaliad gwreiddiol.
-
2. Cydgyfeirio: Pryd Mae Iteriad yn Llwyddiannus?
Nid yw pob ffwythiant \(g(x)\) yn cynhyrchu iteriadau sefydlog. Er mwyn i'r iteriad \(x_{n+1}=g(x_n)\) gydgyfeirio i'r gwreiddyn \(\alpha\), yr amodau cyffredinol a ddefnyddir yn aml yw:
1. \(g(\alpha)=\alpha\) (gwreiddyn yw pwynt sefydlog)
2. \(|g'(\alpha)| < 1\) (cyfangiad lleol) Greddf \(|g'(\alpha)| < 1\) yw: yng nghyffiniau'r ateb, nid yw'r ffwythiant \(g\) yn "rhy serth", felly mae pob iteriad yn dod â gwerth \(x_n\) yn agosach, nid ymhellach. Mae cydgyfeirio hefyd yn cael ei effeithio gan y dyfaliad cychwynnol. Gall yr un ddau ddull lwyddo neu fethu yn dibynnu ar \(x_0\). --- 3. Y Dull Haneru fel Iteriad Syml Er ei fod yn aml yn cael ei ddosbarthu ar wahân, gellir gweld y dull haneru fel dull iterus pwerus iawn. Yr amodau yw: mae'r ffwythiant \(f(x)\) yn barhaus ar y cyfwng \([a,b]\) ac mae newid arwydd: \[ f(a)\cdot f(b) < 0 \] Hynny yw, mae gwreiddyn rhwng \(a\) a \(b\). Yr algorithm: 1. Cyfrifwch y canolbwynt \(c=\frac{a+b}{2}\) 2. Penderfynwch ar yr is-gyfwng sy'n dal i amgáu'r gwreiddyn (yn seiliedig ar y newid arwydd) 3. Ailadroddwch nes cyrraedd y goddefgarwch Mantais y dull hwn: bydd yn sicr o gydgyfeirio os bodlonir yr amod newid arwydd. Yr anfantais: mae'r cydgyfeirio yn gymharol araf oherwydd bod y gwall yn lleihau tua hanner gyda phob iteriad (cydgyfeirio llinol). --- 4. Dull Iteriad Pwynt Sefydlog Dyma'r ffurf fwyaf uniongyrchol o iteriad: \[ x_{n+1} = g(x_n) \] Y camau: 1. Newid \(f(x)=0\) i \(x=g(x)\) 2. Dewiswch ddyfaliad cychwynnol \(x_0\) 3. Iterwch nes bod \(|x_{n+1}-x_n|\) neu \(|f(x_n)|\) yn llai na'r goddefgarwch Y fantais yw symlrwydd. Fodd bynnag, mae'r dull hwn yn sensitif iawn i ddewis \(g(x)\). Ar gyfer yr un hafaliad, mae sawl ffordd o ysgrifennu \(x=g(x)\), ond dim ond rhai ohonyn nhw sy'n cydgyfeirio.
Er enghraifft, os ydym am ddod o hyd i wreiddiau \(f(x)=x^3-2x-5\), gallwn ysgrifennu: - \(x = \sqrt[3]{2x+5}\) fel bod \(g(x)=\sqrt[3]{2x+5}\) Yna rydym yn ailadrodd \(x_{n+1}=\sqrt[3]{2x_n+5}\). Mae llwyddiant yr ailadrodd yn dibynnu a yw \(|g'(x)|<1\) o amgylch y gwreiddyn. --- 5. Dull Newton-Raphson: Ailadrodd Cyflym yn Seiliedig ar Ddeilliadau Mae dull Newton-Raphson yn un o'r dulliau mwyaf poblogaidd oherwydd bod ei gydgyfeirio fel arfer yn gyflym iawn. Y fformiwla ailadrodd yw: \[ x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)} \] Dehongliad: yn \(x_n\), rydym yn llunio tangiad i'r ffwythiant \(f(x)\). Defnyddir croestoriad y tangiad â'r echelin \(x\) fel yr amcangyfrif nesaf. Manteision: - Cydgyfeirio cwadratig (cyflym iawn) os yw'n ddigon agos at y gwreiddyn ac \(f'(\alpha)\neq 0\). Anfanteision: - Angen deilliad \(f'(x)\). - Gall fethu os yw'r dyfaliad cychwynnol yn wael, neu os yw \(f'(x_n)\) yn agos at sero, gan wneud y cam iteriad yn ansefydlog. Defnyddir y dull hwn yn helaeth mewn optimeiddio, modelu ffiseg, a chyfrifiadura peirianneg oherwydd ei effeithlonrwydd pan fo amodau'n ffafriol. --- 6. Dull y Secant: Dewis Arall Newton Heb Ddeilliadau Os yw deilliadau'n anodd eu cyfrifo, mae'r dull secant yn cynnig cyfaddawd. Y prif syniad yw brasamcanu'r deilliad gyda gwahaniaethau meidraidd: \[ f'(x_n)\approx \frac{f(x_n)-f(x_{n-1})}{x_n-x_{n-1}} \] Felly'r fformiwla iteriad yw: \[ x_{n+1}=x_n - f(x_n)\,\frac{x_n-x_{n-1}}{f(x_n)-f(x_{n-1})} \] Mae'r dull hwn yn gofyn am ddau ddyfaliad cychwynnol: \(x_0\) a \(x_1\). Mae ei gyflymder cydgyfeirio yn gyffredinol yn well na haneriad syml a phwynt sefydlog, er ei fod fel arfer ychydig yn arafach na Newton. Fodd bynnag, oherwydd nad oes angen deilliadau arno, mae'r secant yn aml yn fwy ymarferol.
--- 7. Meini Prawf Stopio Mewn cyfrifiad rhifiadol, dylid stopio iteriad pan fydd yn ddigon cywir neu os amheuir nad yw'n cydgyfeirio. Meini Prawf cyffredinol: 1. Gwall rhyng-iteriad bach: \[ |x_{n+1}-x_n|<\varepsilon \] 2. Gwerth ffwythiant yn agos at sero: \[ |f(x_n)|<\varepsilon \] 3. Terfyn iteriad uchaf i atal dolenni diddiwedd: \[ n \le n_{\max} \] Mae'r dewis o oddefgarwch \(\varepsilon\) yn dibynnu ar yr anghenion: gall efelychiadau peirianneg ofyn am oddefiannau tynn, tra bod cyfrifiadau bras yn eithaf rhydd. --- 8. Cymhariaeth Fer o Ddulliau Iteriad I grynhoi: - Haneriad: mwyaf sefydlog, yn cydgyfeirio'n bendant (gyda newid arwydd), ond yn araf. - Pwynt sefydlog: syml iawn, ond nid yw cydgyfeirio bob amser yn cael ei warantu. - Newton-Raphson: cyflym iawn, ond mae angen deilliadau ac mae'n sensitif i ddyfaliadau cychwynnol. - Secant: nid oes angen deilliadau, yn eithaf cyflym, ond gall fod yn llai sefydlog na haneriad. Yn ymarferol, mae'r dewis o ddull yn dibynnu ar natur y ffwythiant, argaeledd deilliadau, yr angen am gyflymder, a sefydlogrwydd. --- Casgliad Dulliau iterus yw asgwrn cefn canfod gwreiddiau rhifiadol ar gyfer hafaliadau anlinellol. Trwy lunio dilyniant o frasamcanion sy'n cael eu diweddaru'n iterus, gallwn agosáu at yr ateb pan nad yw dulliau dadansoddol ar gael. Mae deall cydgyfeirio, y dewis o ddyfaliad cychwynnol, a'r maen prawf stopio yn hanfodol er mwyn i iteriad gynhyrchu gwreiddiau cywir ac effeithlon. Mewn cymwysiadau byd go iawn, defnyddir strategaeth gyfunol yn aml: gan ddechrau gyda dull sefydlog fel haneriad i "gloi" y cyfwng gwreiddyn, yna newid i Newton neu secant i gyflymu cydgyfeirio. Mae hyn yn cyflawni cydbwysedd rhwng dibynadwyedd a chyflymder - dau agwedd werthfawr iawn mewn cyfrifiadura rhifiadol. --- Os dymunwch, gallaf ychwanegu enghraifft gam wrth gam (rhifiadol) o unrhyw un o'r dulliau uchod i wneud yr erthygl yn fwy concrit.
