Cifereca analitiko

Babilona argila tabuleto YBC 7289 (ĉ. 1800–1600 AKE) kun notoj. La proksimumo de la kvadrata radiko de 2 estas kvar sesdekumaj signoj, kiu estas ĉirkaŭ ses dekumaj lokoj. 1 + 24/60 + 51/60² + 10/60³ = 1.41421296...^[1]

Cifereca analitiko estas studo de algoritmoj por solvado de problemoj de kontinua matematiko per diskreta matematiko kaj aparte komputiko. La problemoj estas de kalkulo, cifereca lineara algebro super la reela kaj kompleksa kampoj, solvado de diferencialaj ekvacioj, kaj alia rilatantaj problemoj, ekestantaj el fiziko kaj inĝenierado.

Ĝenerala enkonduko

Multaj problemoj en kontinua matematiko ne havas fermit-forman solvaĵon. Unu ekzemplo estas trovado de integralo de exp(−x²) (la erara funkcio) kaj solvado de ĝenerala polinoma ekvacio de grado kvin aŭ pli alta (vidu teoremon de Abelo-Ruffini). En ĉi tiuj situacioj, oni havas du variantojn: trovi proksimuman solvon uzante asimptotan analitikon aŭ ciferecan solvaĵon. La lasta elekto estas priskriba de cifereca analitiko.

Rektaj kaj ripetaj metodoj

Iuj problemoj estas solveblaj ekzakte per algoritmo. Ĉi tiuj algoritmoj estas nomitaj kiel rektaj. La ekzemploj estas gaŭsa elimino por solvado de sistemoj de linearaj ekvacioj kaj la simpleksa metodo en lineara programado.

Tamen, ankaŭ nerektaj metodoj ekzistas por multaj problemoj. En tiaj okazoj iam eblas uzi ripetan metodon. Ĉi tia metodo startas de diveno kaj trovas sukcesajn proksimumajn kalkulaĵojn, kiuj espereble konverĝas al la solvo. Eĉ se la rekta metodo ekzistas, la ripeta metodo povas esti preferinda ĉar ĝi estas pli rapida, pli stabila aŭ pli preciza (en okazo de uzado de realaj kalkuliloj).

Diskretigo

La kontinua problemo devas iam esti anstataŭigitaj per nekontinua problemo kies solvaĵo estas proksimuma solvon de la kontinua problemo; ĉi tiu procezo estas nomita nekontinuigo. Ekzemple, la solvo de diferenciala ekvacio estas funkcio. Ĉi tiu funkcio devas esti prezentita per finia kvanto de datumoj, ekzemple per ĝia valoro je finia nombro de punktoj je ĝia domajno, malgraŭ ke ĉi tiu domajno povas estas kontinuaĵo.

La generacio kaj disvastigo de eraroj

La studado de eraroj formas gravan parton de cifereca analitiko. Ekzistas kelkaj fontoj de eraroj en la solvado de la problemo. rondigaj eraroj ekestas ĉar estas neeble prezenti ĉiujn reelajn nombrojn ekzakte per maŝino kun finia memoro (tiaj estas ĉiuj praktikaj ciferecaj komputiloj). Trunkaj eraroj okazas kiam oni finas iteracion aŭ oni aproksimas solvaĵon, kaj la solvo diferencas de la ekzakta solvo. Simile, diskretigo liveras diskretigan eraron ĉar la solvo de la diskreta problemo ne koincidas kun la solvo de la kontinua problemo.

Kiam eraro estas generita, ĝi ĝenerale disvastiĝos tra la kalkulo. Tio kondukas al la nocio de cifereca stabileco: algoritmo estas ciferece stabila se eraro, kiam ĝi estas generita, ne kresku tro dum la kalkulo. Tio eblas se la problemo estas bonkonduta, kiu signifas ke la solvaĵo ŝanĝiĝas per nur eta kvanto se oni ŝanĝas la datumojn per eta kvanto. Aliflanke, se problemo estas malbonkonduta, tiam eventuala eraro en la datumoj multe kreskos.

Do, algoritmo kiu solvas bonkondutan problemon estos aŭ ciferece stabila aŭ ciferece malstabila. Arto de cifereca analitiko estas trovi stabilan algoritmon por solvi bonkondutan matematikan problemon. Rilatanta arto estas trovi stabilan algoritmon por solvi malbonkondutajn problemojn, kiuj ĝenerale postulas trovi bonkondutan problemon kies solvaĵo estas proksima al tiu de la malbonkonduta problemo kaj solvi ĉi tiun bonkondutan problemon anstataŭe.

Aplikoj

Oni kutime aplikas algoritmojn de cifereca analitiko por solvi problemojn en scienco kaj inĝenierado. Ekzemploj estas la projektado de strukturoj kiel pontoj kaj aviadiloj (vidu ĉe komputada fiziko) kaj komputada fluidodinamiko, vetero-prognozado, modeli klimaton, la analizo kaj desegnado de molekuloj (komputada kemio), kaj trovi naftobasenojn. Fakte, preskaŭ ĉiuj superkomputiloj rulas ciferecanalitikajn algoritmojn.

Tial, rendimento ludas gravan rolon kaj heŭristika metodo ofte povas esti preferita metodo kun solida teoria fundamento, ĉar ĝi estas pli efika. Ĝenerale, cifereca analitiko uzas empiriajn rezultojn de kalkulado, kun validaj novaj metodoj por analizi problemojn, kvankam ĝi kompreneble ankaŭ utiligas matematikajn aksiomojn, teoremojn kaj pruvojn.

Studotemoj

La kampo de cifereca analitiko estas dividebla en diversajn subfakojn laŭ la tipo de problemoj solvotaj.

Komputi valorojn de funkcioj

Unu el la plej simplaj problemoj estas kalkuli la valoron de funkcio ĉe donita punkto. Por polinomoj la Hornera algoritmo estas ofte pli efika ol la evidenta metodo. Ĝenerale, gravas taksi kaj regi rondigajn erarojn ekestantajn pro la uzado de flosanta komo.

Interpoli, ekstrapoli kaj regreso

Interpoli solvas la jenan problemon: laŭ la donita valoro de iu nekonata funkcio ĉe kelkaj punktoj, kiun valoron havas tiu funkcio ĉe alia punkto inter la donitaj punktoj? Tre simpla metodo estas uzi linearan interpolon, kiu supozas ke la nekonata funkcio estas lineara inter ĉiu paro de sinsekvaj punktoj. Ĉi tiu povas esti ĝeneraligita al polinoma interpolo, kiu estas iam pli preciza sed suferas de la Runge-a fenomeno. Aliaj interpolaj metodoj uzas lokigitajn funkciojn, ekzemple splajnojn aŭ ondetojn.

Eksterpoli similas al interpoli, sed nun oni volas trovi la valoron de la nekonata funkcio ĉe punkto ekster la donitaj punktoj.

Regreso estas ankaŭ simila, sed ĝi agnoskas ke la datumoj estas neprecizaj. Laŭ donitaj punktoj, kaj laŭ mezuro de la valoro de iu funkcio ĉe tiuj punktoj (kun eraro), ni bezonas taksi la nekonatan funkcion. La metodo de plej malgrandaj kvadratoj estas unu populara metodo por atingi tion.

Solvi ekvaciojn kaj sistemojn de ekvacioj

Alia fundamenta problemo estas komputi la solvon de iu donita ekvacio. Du kazoj estas kutime konsiderindaj, depende de ĉu la ekvacio estas lineara aŭ ne.

Oni multe penis evoluigi metodojn por solvi sistemojn de linearaj ekvacioj. Normaj metodoj estas Gaŭso-Jordana elimino kaj LU-faktorigo. Iteraciaj metodoj kiel la konjugita gradienta metodo estas kutime preferitaj por grandaj sistemoj.

Radiko-trovantaj algoritmoj estas utilaj por solvi nelinearajn ekvaciojn (ili estas tiel nomitaj ĉar radiko de funkcio estas argumento por kiu la funkcio donas nulon). Se la funkcio estas diferencialebla kaj la derivaĵo estas sciata, tiam la Neŭtona metodo estas populara elekto. Linearigo estas alia tekniko por solvi nelinearajn ekvaciojn.

Optimumigo

Ĉefa artikolo: Optimumigo (matematiko).

Optimumigaj problemoj postulas trovi la punkton kie la funkcio estas maksimuma. Ofte la punkto devas plenumi iujn kondiĉojn.

La kampo de optimumigo estas disigebla en kelkajn subtemojn, depende de la formo de la objekta funkcio kaj la kondiĉo. Ekzemple, lineara programado pritraktas la okazon ke kaj la objekta funkcio kaj la kondiĉo estas lineara. Fama metodo en lineara programado estas la simpleksa metodo.

La metodo de multiplikantoj de Joseph-Louis Lagrange povas redukti optimumigajn problemojn kun limigoj al nelimigitaj problemoj.

Kalkuli integralojn

Ĉefa artikolo: Cifereca integralo.

Cifereca integralado (aŭ cifereca kvadraturo), serĉas por la valoro de difinita integralo. Popularaj metodoj uzas formulon de Neŭtono-Cotes, ekzemple la mezpunkta regulo aŭ regulo de Simpson) aŭ Gaŭsa kvadraturo. Ĉi tiuj metodoj dependas de strategio "dividi kaj venki", per kiu oni apartigas integralon sur relative granda aro en integraloj sur pli malgrandaj aroj. En pli altaj dimensioj, kie ĉi tiuj metodoj iĝas neeblige multekostaj laŭ komputada peno, oni povas uzi metodojn de Monte-Carlo, aŭ, en mezgrandaj dimensioj, la metodon de maldensaj kradoj.

Solvi diferencialajn ekvaciojn

Ĉefaj artikoloj: Ciferecaj ordinaraj diferencialaj ekvacioj, Ciferecaj partaj diferencialaj ekvacioj.

Cifereca analitiko estas ankaŭ uzata por komputi diferencialajn ekvaciojn, kaj ordinarajn diferencialajn ekvaciojn kaj diferencialajn ekvaciojn en partaj derivaĵoj.

Partaj diferencialaj ekvacioj estas solveblaj, unue diskretigante la ekvacion, kondukante ĝin en finidimensian subspacon. Ĉi tiu estas farebla per finia elementa metodo, finia diferenca metodo, aŭ (aparte en inĝenierado) finia volumena metodo. La teoria pravigo de ĉi tiuj metodoj ofte koncernas teoremojn el funkcionala analitiko. Tio reduktas la problemon al la solvado de algebra ekvacio.

Historio

La kampo de cifereca analitiko inventiĝis je multaj jarcentoj antaŭ la invento de modernaj komputiloj. Lineara interpolo estis jam uzata antaŭ pli ol 2000 jaroj. Multaj grandaj matematikistoj de la pasinto okupis sin per cifereca analitiko, kiel estas evidente pro la nomoj de gravaj algoritmoj, ekzemple Neŭtona metodo, Lagrange-a interpola polinomo, Gaŭsa elimino, kaj Eŭlera metodo.

Por faciligi kalkuladojn permane, grandaj libroj produktiĝis kun formuloj kaj tabeloj de datumoj kiel interpolaj punktoj kaj funkciaj koeficientoj. Uzi tiujn tabelojn, ofte kalkulitaj por 16 dekumaj lokoj aŭ pli por iuj funkcioj, oni povus trovi valorojn por substitui en la formulojn donitajn kaj atingi tre bonan ciferecan takson de iuj funkcioj. La elstara laboro en la kampo estas la NIST-eldono redaktita de Abramowitz kaj Stegun, milpaĝa libro de tre granda nombro de kutime uzataj formuloj kaj funkcioj kaj iliaj valoroj ĉe multaj punktoj. La funkciaj valoroj estas ne tre utilaj kiam komputilo estas disponebla, sed la granda listaro de formuloj povas ankoraŭ esti tre oportuna.

La mekanika kalkulilo estis ankaŭ ellaborita kiel ilo por mana kalkulado. Ĉi tiuj kalkuliloj evoluis en elektronikajn komputilojn en la 1940-aj jaroj, kaj estis tiam fundamente, ke ĉi tiuj komputiloj estis ankaŭ utilaj por administraj celoj. Sed la invento de la komputilo ankaŭ influis la kampon de cifereca analitiko, ĉar eblis solvi pli longajn kaj pli komplikajn kalkulojn.

Programaroj

Nuntempe, plejmultaj algoritmoj estas realigitaj kaj ruliĝas komputile. La Netlib-deponejo enhavas diversajn kolektojn de programaraj metodoj por ciferecaj problemoj, plejparte en Fortran (programlingvo) kaj C. Ekzistas proprietaj produktoj kiuj realigas diversajn ciferecajn algoritmojn, ekzemple la bibliotekoj IMSL kaj NAG; libera alternativo estas la GNU Scienca Biblioteko. Malsaman metodon prenis la Cifereca Recepta biblioteko, kiu emfazas kompreni klasikajn algoritmojn. (Iuj konsideras tion forteco; aliaj bedaŭras la erarojn kaj malbonan konsilon.)

Aliaj popularaj lingvoj por cifereca komputado estas MATLAB, IDL, kaj Pitono. Ĉi tiuj estas interpretitaj programlingvoj, sed ili ebligas pli rapidan evoluigon kaj prototipadon, kaj se necese povas esti konvertitaj al Fortran kaj C por plia rapido. Rapido vaste varias: dum vektoraj kaj tabelaj operacioj ofte estas rapidaj, skalaraj iteracioj povasvarii laŭ pli ol ordo de grando.^[2]^[3]

Multaj komputilaj algebraj sistemoj, ekzemple Mathematica kaj Acero (liberaj programaraj sistemoj inkluzive de Maxima, Aksiomo, calc kaj Yacas), uzeblas por ciferecaj kalkuloj. Ilia forteco tipe kuŝas en signa kalkulado.

Multaj komputilaj algebraj sistemoj, ekzemple Mathematica, havas la avantaĝon de arbitre preciza aritmetiko, kiu povas liveri pli ekzaktajn rezultojn.

Kalkultabelilo estas uzebla por solvi simplajn problemojn rilate al cifereca analitiko.