Թվային մեթոդներ

Թվային անալիզը մաթեմատիկական անալիզի (դիսկրետ անալիզից տարբեր) խնդիրների համար, թվային մոտարկում (ի տարբերություն սիմվոլների ձևափոխության) օգտագործող ալգորիթմների ուսումնասիրություն է։ Թվային անալիզը, բնականաբար, կիրառություն է գտնում ինժեներական և ֆիզիկական գիտությունների բոլոր բնագավառներում, բայց 21-րդ դարում նաև կյանքի գիտությունները, հասարակական գիտությունները, բժշկությունը, բիզնեսը և նույնիսկ արվեստները փոխառել են գիտական ​​հաշվարկների տարրեր։ Հաշվողական հզորության աճը հեղափոխել է ռեալիստական ​​մաթեմատիկական մոդելների օգտագործումը գիտության և ճարտարագիտության մեջ, և աշխարհի այս մանրամասն մոդելները կյանքի կոչելու համար պահանջվում է նուրբ թվային վերլուծություն։ Օրինակ, սովորական դիֆերենցիալ հավասարումները հայտնվում են երկնային մեխանիկայում (կանխատեսում են մոլորակների, աստղերի և գալակտիկաների տեղաշարժերը), թվային գծային հանրահաշիվը կարևոր է տվյալների վերլուծության համար, Ստոխաստիկ դիֆերենցիալ հավասարումները և Մարկովի շղթաները էական են բժշկության և կենսաբանության մեջ՝ կենդանի բջիջները մոդելավորելու համար։

Մինչև ժամանակակից համակարգիչների հայտնվելը, թվային մեթոդները հաճախ կախված էին ձեռքի ինտերպոլացիոն բանաձևերից, որ կիրառվում էին մեծ տպագիր տվյալների աղյուսակների նկատմամբ։ 20-րդ դարից կեսերից պահանջվող ֆունկցիաների հաշվարկները կատարվում են համակարգիչներ օգնությամբ, բայց նշված բանաձևերից շատերը, այնուամենայնիվ, շարունակում են օգտագործվել որպես ծրագրային ալգորիթմների մաս։

Թվային տեսակետը գալիս է դեռևս շատ վաղ մաթեմատիկական գրություններից։ Բաբիլոնյան կավե ցուցանակը՝ YBC 7289, տալիս է վաթսունական հաշվարկային համակարգում քառակուսի արմատ 2-ի մոտարկումը չորս վաթսունական թվային համակարգում, որը միավոր քառակուսու անկյունագծի երկարությունն է։

Թվային անալիզը շարունակում է այս վաղ ավանդույթը՝ ճշգրիտ սիմվոլիկ պատասխանների փոխարեն, որոնք կարող են իրական աշխարհի չափումների նկատմամբ կիրառվել միայն թվերով փոխարինելով, տալ մոտավոր լուծումներ նշված սխալի սահմաններում։

Ընդհանուր ներածություն
Թվային անալիզի ընդհանուր նպատակը բարդ խնդիրներին մոտավոր, բայց ճշգրիտ լուծումների մեթոդների նախագծումն ու վերլուծությունն է, որոնց բազմազանությունը ներկայացված է ներքո.
 Նորարական թվային մեթոդները կարևոր են եղանակի թվային կանխատեսումը ապահովելու համար։
 Տիեզերանավի հետագիծը հաշվելը պահանջում է սովորական դիֆերենցիալ հավասարումների համակարգի ճշգրիտ թվային լուծում։
 Ավտոմեքենաների ընկերությունները կարող են բարելավել իրենց տրանսպորտային միջոցների անվտանգությունը՝ օգտվելով ավտովթարների համակարգչային սիմուլյացիանեից։ Նման սիմուլյացիաները, ըստ էության, բաղկացած են մասնակի դիֆերենցիալ հավասարումների թվային լուծումից։
 Հեջ ֆոնդերը (մասնավոր ներդրումային ֆոնդեր) օգտագործում են գործիքներ, թվային անալիզի բոլոր ոլորտներից, փորձելով`բաժնետոմսերի արժեքները և ածանցյալ ֆինանսները ավելի ճշգրիտ հաշվարկել, քան շուկայի այլ մասնակիցներ։ 
 Ավիաընկերությունները օգտագործում են օպտիմիզացման բարդ ալգորիթմներ՝ տոմսերի գները, ինքնաթիռների և անձնակազմի հանձնարարությունները և վառելիքի կարիքները որոշելու համար։ Պատմականորեն, նման ալգորիթմները մշակվել են գործողությունների հետազոտության ոլորտում։
 Ապահովագրական ընկերությունները թվային ծրագրերն օգտագործում են ակտուարական վերլուծության համար։
Այս բաժնի մնացած մասը ներկայացնում է թվային անալիզի մի քանի կարևոր թեմաներ։

Պատմություն
Թվային անալիզի բնագավառը զարգացել է ժամանակակից համակարգիչների գյուտից դարեր առաջ։ Գծային ինտերպոլացիան օգտագործվում էր դեռևս 2000 տարի առաջ։ Անցյալի մեծ մաթեմատիկոսներy զբաղվում էին թվային անալիզով, ինչն ակնհայտ երևում է կարևոր ալգորիթմների անուններից, ինչպիսիք են Նյուտոնի մեթոդ, Լագրանժի բազմանդամային ինտերպոլացիա, Գաուսի մեթոդ կամ Էյլերի մեթոդ։

Ձեռքով հաշվարկները հեշտացնելու համար պատրաստվել են մեծ գրքեր` բանաձևերով և տվյալների աղյուսակներով, ինչպիսիք են ինտերպոլացիոն կետերը և ֆունկցիայի գործակիցները։ Օգտագործելով այս աղյուսակները, որ հաճախ որոշ ֆունկցիաների համար հաշվարկում են մինչև 16 կամ ավելի տասնորդական նիշքեր, հնարավոր է որոշ ֆունկցիաների համար հասնել շատ լավ թվային գնահատականների։ Ստանդարտների ազգային ինստիտուտի կողմից տպագրվել է 1000+ էջերից բաղկացած գիրքը, որ պարունակում է հաճախ օգտագործվող բանաձևերն ու ֆունկցիները և դրանց արժեքները շատ կետերում։ Համակարգչի հասանելիության պարագայում ֆունկցիայի արժեքներն այլևս շատ օգտակար չեն, բայց բանաձևերի մեծ ցանկը դեռևս կարող է շատ հարմար լինել։

Մեխանիկական հաշվիչները մշակվել են որպես գործիք ձեռքով հաշվարկների համար։ 1940-ականներին դրանք վերածվեցին էլեկտրոնային համակարգիչների, և այնուհետ պարզվեց որ այս համակարգիչներն օգտակար են նաև վարչական նպատակների համար։ Համակագիչների մուտքը ազդեցություն գործեց թվային անալիզի ոլորտի վրա, քանի որ այժմ հնարավոր է կատարել ավելի երկար և բարդ հաշվարկներ։

Ուղիղ և իտերացիոն մեթոդներ

Ուղիղ մեթոդները խնդրի լուծումը հաշվարկում են վերջավոր քանակի քայլեր կատարելով։ Այս մեթոդները ճշգրիտ պատասխան կտան, եթե դրանք իրականացվեն անսահման ճշգրիտ թվաբանությամբ։ Օրինակները ներառում են Գաուսի մեթոդը, QR ֆակտորիզացիայի մեթոդը, որոնք կիրառվում են գծային հավասարումների համակարգերի լուծման համար և սիմպլեքս մեթոդը՝ գծային ծրագրավորման համար։ Գործնականում օգտագործվում է վերջավոր ճշգրտություն, իսկ արդյունքը ճշգրիտ լուծման մոտարկումն է (կայունությունը ենթադրելով)։

Ի հակադրություն ուղիղ մեթոդների, իտերացիոն մեթոդների դեպքում, չի ենթադրվում, որ կավարտվեն վերջավոր քայլերով։ Սկսած նախնական ենթադրությունից, իտերացիոն մեթոդները ձևավորում են հաջորդական մոտարկումներ, որոնք  ճշգրիտ լուծմանը զուգամիտում են միայն սահմանին։ Զուգամիտող թեստը հաճախ ներառում է մնացորդը, որպեսզի որոշենք, թե երբ է հայտնաբերվել բավարար ճշգրիտ լուծում։ Նույնիսկ անվերջ ճշգրիտ թվաբանություն օգտագործելով, ընդհանուր առմամբ այս մեթոդները վերջավոր քայլերի միջոցով լուծմանը չեն հասնի։ Օրինակները ներառում են Նյուտոնի մեթոդը, բիսեկցիայի մեթոդը և Յակոբի մեթոդը։ Հաշվարկային մատրիցային հանրահաշվում իտերացիոն մեթոդներն անհրաժեշտ են ծավալուն խնդիրների համար։

Թվային անալիզում իտերացիոն մեթոդներն ավելի տարածված են, քան ուղիղ մեթոդները։ Որոշ մեթոդներ սկզբունքորեն ուղիղ են, բայց սովորաբար օգտագործվում են այնպես, կարծես՝ չեն։ Այս մեթոդների համար ճշգրիտ լուծում ստանալու համար անհրաժեշտ քայլերի քանակը այնքան մեծ է, որ մոտարկումն ընդունելի է նույն կերպ, ինչպես իտերացիոն մեթոդինը։

Դիսկրետացում
Անընդհատ խնդիրները երբեմն պետք է փոխարինվեն դիսկրետ խնդիրներով, որոնց լուծումը ինչպես հայտի է մոտարկում է անընդհատ խնդրի լուծմանը։ Այս գործընթացը կոչվում է 'դիսկրետացում'։ Օրինակ, դիֆերենցիալ հավասարման լուծումը ֆունկցիա է։ Այդ ֆունկցիան պետք է ներկայացվի վերջավոր տվյալների միջոցով, օրինակ, նրա որոշման տիրույթի վերջավոր թվով կետերի արժեքներով, նույնիսկ, եթե այդ տիրույթը կոնտինիում է։

Սխալների առաջացում և տարածում
Սխալների ուսումնասիրությունը թվային անալիզի կարևոր մաս է կազմում։ Խնդրի լուծման ընթացքում սխալների առաջացման մի քանի պատճառներ կան։

Կլորացում
Կլորացման սխալները ծագում են այն պատճառով, որ բոլոր իրական թվերը անհնար է ներկայացնել վերջավոր հիշողություն ունեցող մեքենայում։

Կրճատման և դիսկրետացման սխալ
Կլորացման սխալներ են գրանցվում, երբ իտերացիոն մեթոդն ավարտվել է, կամ մաթեմատիկական պրոցեսը մոտարկվել է, իսկ մոտարկված լուծումը տարբերվում է ճշգրիտ լուծումից։ Նմանապես, դիսկրետացումն առաջ է բերում դիսկրետացման սխալ, քանի որ դիսկրետ խնդրի լուծումը չի համընկնում անընդհատ խնդրի լուծման հետ։ Օրինակ,  իտերացիայի միջոցով, ինչպես կողքի վահանակում,  հավասարման լուծումը հաշվելիս, մոտավորապես 10 իտերացիայից հետո, կարելի է եզրականացնել, որ արմատը 1.99 Է (օրինակ)։ Հետևաբար, կլորացման սխալը 0,01 է։

Սխալն առաջանալուց հետո, այն, որպես կանոն, այն կտարածվի հաշվարկների միջոցով։ Օրինակ, արդեն հայտնի է, որ հաշվիչի (կամ համակարգչի) վրա + գործողությունը ճշգրիտ չէ։ Այստեղից հետևում է, որ  տեսակի հաշվարկը, էլ ավելի ճշգրիտ չէ։

Կլորացման սխալն առաջ է գալիս, երբ մաթեմատիկական գործողությունները մոտարկվում են։

Հաշվարկային կայունություն և լավ ձևակերպված խնդիրներ
Հաշվարկային կայունությունը հասկացություն է թվային անալիզում։ Ալգորիթմը համարվում է 'թվային կայուն', եթե սխալը, ինչ պատճառով էլ որ այն ծագած լինի, հաշվարկի ընթացքում շատ ավելի մեծ չի դառնում։ Սա տեղի է ունենում, եթե խնդիրը «լավ է ձևակերպված», ինչը նշանակում է, որ խնդրի տվյալների քանակական փոքր փոփոխության դեպքում, լուծումը ևս փոքր փոփոխություն է կրում։ Ընդհակառակը, եթե խնդիրը «վատ է ձևակերպված», ապա տվյալների ցանկացած փոքր սխալը մեծ սխալի կվերաճի։

Թե բուն խնդիրը, թե նրա լուծման համար օգտագործվող ալգորիթմը կարող են լինել 'լավ-ձևակերպված' կամ 'վատ-ձևակերպված', և ցանկացած համադրություն հնարավոր է։

Այսպիսով, ալգորիթմը, որը լուծում է լավ ձևակերպված խնդիրը, կարող է լինել կամ հաշվարկային կայուն, կամ հաշվարկային անկայուն։ Թվային անալիզի արվեստը՝ մաթեմատիկորեն ճշգրիտ ձևակերպված խնդրի լուծման համար, կայուն ալգորիթմ գտնելն է։ Օրինակ, 2-ի քառակուսի արմատ հաշվելը (որը մոտավորապես հավասար է 1.41421) ճշգրիտ ձևակերպված խնդիր է։ Շատ ալգորիթմներ լուծում են այս խնդիրը `սկսելով x0 նախնական մոտարկումից մինչև , օրինակ x0 = 1.4, և այնուհետև հաշվելով լավացնում կանխատեսումները x1, x2, և այլն։ Այսպիսի մեթոդներից է հայտնի Բաբիլոնյան մեթոդը, որ ներկայացվում է այս կերպ xk+1 = xk/2 + 1/xk։ Մեկ այլ 'մեթոդ X'-ը ներկայացվում է xk+1 = (xk2 − 2)2 + xk։ Յուրաքանչյուր մեթոդի մի քանի իտերացիան հաշվվում է ներքո բերված աղյուսակում, x0 = 1.4 և x0 = 1.42 սկզբնական ենթադրություններով։

Նկատենք, որ Բաբիլոնյան մեթոդը անկախ սկզբնական ենթադրության արագ է զուգամիտում, մինչդեռ X մեթոդը x0 = 1.4 սկզբնական ենթադրության դեպքում չափազանց դանդաղ է զուգամիտում և տարամիտում է x0 = 1.42 սկզբնական ենթադրության դեպքում։ Այսպիսով Բաբիլոնյան մեթոդը թվայնորեն կայուն է, մինչդեռ X մեթոդը թվայնորեն անկայուն է։
Թվային կայունության վրա ազդում է այն, թե մեքենան քանի տասնորդական նիշք է պահում, եթե մեքենան միայն չորս տասնորդական նիշք է պահում, հետևյալ համարժեք ֆունկցիաները նշանակալիության կորստի լավ օրինակ են․  

Համեմատելով
 
և

արդյունքները,
 պարզ է, որ նշանակալիության կորուստը հսկայական ազդեցություն է գործում արդյունքների վրա, նույնիսկ այն դեպքում երբ երկու ֆունկցիան համարժեք են, ինչպես ցույց է տրված վերևում
 
 Անսահման ճշգրտությամբ հաշվարկված ցանկալի արժեքը 11.174755 է ...

Ուսումնասիրության ոլորտները
Թվային անալիզի բնագավառը ներառում է շատ ենթաճյուղեր։ Ահա հիմնականներից մի քանիսը․

Ֆունկցիաների արժեքների հաշվելը

Ամենապարզ խնդիրներից մեկը տվյալ կետում ֆունկցիայի գնահատումն է։ Ամենապարզ մոտեցումը՝ թիվը պարզապես բանաձևում տեղադրելը, երբեմն այնքան էլ արդյունավետ չէ։ Բազմանդամների համար, լավագույն եղանակը Հորների սխեման օգտագործելն է, քանի որ այն նվազեցնում է բազմապատկման և գումարման անհրաժեշտ քանակը։ Ընդհանուր առմամբ կարևոր է լողացող կետի թվաբանության օգտագործումից բխող կլորացման սխալները գնահատելը և վերահսկելը։

Ինտերպոլացիա, էքստրապոլացիա և ռեգրեսիա
Ինտերպոլացիան լուծում է հետևյալ խնդիրը․ ելնելով որևէ անհայտ ֆունկցիայի արժեքներից մի շարք կետերում, գտնել այդ ֆունկցիայի արժեքը որևէ այլ կետում, որն ընկած է տված կետերի միջակայքում։

Էքստրապոլացիան շատ նման է ինտերպոլացիային, այն տարբերությամբ, որ այս դեպքում պետք է գտնել անհայտ ֆունկցիայի արժեքը, տված կետերի միջակայքից դուրս գտնվող կետում։

Ռեգրեսիան նույնպես նման է, բայց այն հաշվի է առնում, որ տվյալները ճշգրիտ չեն։ Տված են մի քանի կետեր և ինչ որ ֆունկցիայի արժեքի չափումը այդ կետերում (սխալով), պետք է գտնել անհայտ ֆունկցիան։ Նվազագույն քառակուսիների մեթոդը դրան հասնելու մեկ եղանակ է։

Հավասարումների և հավասարումների համակարգի լուծում
Մեկ այլ հիմնարար խնդիր է որևէ հավասարման լուծումը հաշվելը։ Ընդհանուր առմամբ երկու տարբերակ է առանձնացվում՝ հավասարումը գծային է, թե՝ ոչ։ Օրինակ,   հավասարումը գծային է, մինչդեռ  հավասարումը՝ ոչ։.

Շատ ջանք է գործադրվել գծային հավասարումների համակարգերի լուծման մեթոդների մշակման համար։ Ստանդարտ ուղիղ մեթոդները, այսինքն, մեթոդներ, որ օգտագործում են որոշ մատրիցայի տրոհում, Գաուսի մեթոդը, LU տրոհումը, սիմետրիկ մատրիցաների և դրական որոշակի մատրիցաների համար Խոլեցկու տրոհումը և QR տրոհումը՝ ոչ քառակուսի մատրիցաների համար։ Իտերացիոն մեթոդները, ինչպիսիք են Յակոբի մեթոդը, Գաուսի մեթոդը, հաջորդական րելաքսացիայի մեթոդը և լծորդ գրադիենտ մեթոդը մեծ համակարգերի համար սովորաբար նախընտրելի են։ Ընդհանուր իտերատիվ մեթոդները կարող են մշակվել`օգտագործելով մատրիցայի բաժանում։

Արմատներ գտնելու ալգորիթմները օգտագործվում են ոչ գծային հավասարումների լուծման համար։ Եթե ֆունկցիան ածանցելի է և ածանցյալը հայտնի է, ապա Նյուտոնի մեթոդը ընդունելի ընտրություն է։ Գծայնացումը ոչ գծային հավասարումների լուծման մեկ այլ մեթոդ է։

Սեփական արժեքի կամ եզակի արժեքի խնդիրները
Մի քանի կարևոր խնդիրներ կարող են ձևակերպվել սեփական կամ եզակի արժեքի տարանջատման տերմինների միջոցով։ Օրինակ,  սպեկտրային պատկերի սեղմման ալգորիթմը  հիմնված է եզակի արժեքի տարանջատման վրա։ Վիճակագրության մեջ համապատասխան գործիքը կոչվում է հիմնական բաղադրիչի մեթոդ։

Օպտիմիզացիա

Օպտիմիզացիոն խնդիրները փնտրում են կետը, որում տվյալ ֆունկցիան առավելագույնի (կամ նվազագույնի) հասնում։ Հաճախ կետը նաև պետք է բավարարի որոշ սահմանափակումների։

Կախված նպատակային ֆունկցիայի ձևից և սահմանափակումներից օպտիմիզացիայի ոլորտը այնուհետ բաժանվում է մի քանի ենթաճյուղերի։ Օրինակ, գծային ծրագրավորման մեջ, թե նպատակային ֆունկցիան և թե սահմանափակումները գծային են։ Գծային ծրագրավորման հայտնի մեթոդ է սիմպլեքս մեթոդը։

Լագրանժի բազմապատկիչների մեթոդը կարող է օգտագործվել սահմանափակումներով օպտիմիզացիոն խնդիրները մեղմացնելու համար, բերելով դրանք առանց սահմանափակումների օպտիմիզացիոն խնդիրների։

Ինտեգրալների գնահատում

Թվային ինտեգրումը, հայտնի նաև որպես թվային կվադրատուրա, հարցնում է որոշակի ինտեգրալի արժեքը։ Հայտնի մեթոդները օգտագործում են Նյուտոն-Կոթսի բանաձևերից մեկը կամ Գաուսյան կվադրատուրան։ Այս մեթոդները հիմնվում են "բաժանիր, որ տիրես" ռազմավարության վրա, որի համաձայն համեմատաբար մեծ բազմության վրա ինտեգրալները տրոհվում են ինտեգրալների փոքր բազմությունների վրա։ Ավելի մեծ չափայնության դեպքում, որտեղ այս մեթոդները հաշվարկների առումով չափազանց թանկարժեք են դառնում, կարելի է օգտագործել Մոնտե-Կարլոյի կամ քվազի-Մոնտե-Կառլոյի մեթոդները, կամ ավելի համեստ չափայնության դեպքերում՝ sparse grid մեթոդը։

Դիֆերենցիալ հավասարումներ

Թվային անալիզը կապված է նաև դիֆերենցիալ հավասարումների, թե սովորական և թե մասնակի դիֆերենցիալ հավասարումների լուծումների հաշվարկի (մոտարկման եղանակով) հետ։

Մասնակի դիֆերենցիալ հավասարումները լուծվում են դիսկրետացման միջոցով սկզբում բերելով այն վերջավոր չափանի ենթատատարածք։ Դա կարելի է անել վերջավոր տարրի մեթոդի, վերջավոր տարբերության մեթոդի, կամ (մասնավորապես ճարտարագիտության մեջ) վերջավոր ծավալի մեթոդի միջոցով։ Այս մեթոդների տեսական հիմնավորումը հաճախ ներառում է ֆունկցիոնալ անալիզի թեորեմները։

Ծրագրային ապահովում

Քսաներորդ դարավերջից ի վեր, ալգորիթմների մեծամասնությունն իրականացվում է ծրագրավորման տարբեր լեզուներով։  Netlib շտեմարանը պարունակում է տարբեր ծրագրային փաթեթներ թվային խնդիրների համար, հիմնականում Fortran և C ծրագրավորման լեզուներով։ IMSL թվային գրադարանը և NAG գրադարանները պարունակում են կոմերցիալ ծրագրային արտադրանքներ, որոնք իրականացնում են տարբեր թվային ալգորիթմներ։ Դրանց այլընտրանք է GNU գիտական գրադարանը։

Գոյություն ունեն մի քանի հայտնի թվային հաշվողական հավելվածներ, ինչպիսիք են MATLAB, TK Solver, S-PLUS, և IDL, ինչպես նաև ազատ և բաց կոդերով այլընտրանքներ, ինչպիսիք են  FreeMat, Scilab, GNU Octave (Matlab-ին նման), և IT++ (C++ գրադարան)։ Գոյություն ունեն մաև այնպիսի ծրագրավորման լեզուներ, ինչպիսիք են R (S-PLUS-ի նման) և Python, իրենց գրադարաններով՝ NumPy, SciPy և SymPy։ Արդյունավետությունը մեծապես տատանվում է․ մինչ վեկտորային և մատրիցային գործողությունները սովորաբար շատ արագ են, սկալյար ցիկլերը կարող են տարբերվել կարգով։

Շատ հանրահաշվական համակարգչային համակարգեր (CAS), ինչպիսին Mathematica-ն է, շահում են կամայական ճշտության թվաբանության հասանելիությունից, ինչը կարող է ապահովել ավելի ճշգրիտ արդյունքներ։

Բացի այդ, էլեկտրոնային աղյուսակների համար նախատեսված ցանկացած ծրագրային ապահովում կարող է օգտագործվել թվային անալիզին վերաբերող պարզ խնդիրներ լուծելու համար։

Ծանոթագրություններ 

Հաշվողական գիտություններ
Թվային մեթոդներ