Агуулгыг алгасах

Язгуур олох Ньютоны арга

Энэ бол Исаак Ньютоны 1664 оны орчим зохион бүтээсэн итератив арга юм. Гэвч энэ аргыг заримдаа Рафсоны арга гэж бас нэрлэдэг, учир нь Рафсон Ньютоноос хэдэн жилийн дараа ижил алгоритмыг зохион бүтээсэн боловч түүний өгүүлэл хамаагүй эрт хэвлэгдсэн.

Бодлого дараах байдалтай. Дараах тэгшитгэл өгөгдсөн:

$$f(x) = 0$$

Бид тэгшитгэлийг бодохыг хүсэж байна. Илүү нарийвчлалтай хэлбэл түүний язгууруудын нэгийг олохыг хүсэж байна (язгуур оршин байна гэж үзнэ). $f(x)$ нь $[a, b]$ интервал дээр тасралтгүй бөгөөд дифференциалчлагдах гэж үзнэ.

Алгоритм

Алгоритмын оролтын параметрүүд нь зөвхөн $f(x)$ функцээс гадна алгоритмын эхлэх эхний ойролцоолол болох ямар нэг $x_0$-оос тогтоно.

plot_f(x)

Бид $x_i$-г аль хэдийн тооцоолсон гэж бодъё, $x_{i+1}$-г дараах байдлаар тооцоолъё. $x = x_i$ цэг дээр $f(x)$ функцийн графикт шүргэгч татаж, энэ шүргэгч $x$-тэнхлэгтэй огтлолцох цэгийг ол. $x_{i+1}$-г олсон цэгийн $x$-координаттай тэнцүү тавьж, бид бүх процессыг эхнээс нь давтана.

Дараах томьёог олоход хэцүү биш,

$$ x_{i+1} = x_i - \frac{f(x_i)}{f^\prime(x_i)} $$

Эхлээд бид $f(x)$-ийн уламжлал болох $f'(x)$ налууг тооцоолж, дараа нь шүргэгчийн тэгшитгэлийг тодорхойлно, энэ нь

$$ y - f(x_i) = f'(x_i)(x - x_i) $$

Шүргэгч нь x-тэнхлэгтэй $y = 0$ ба $x = x_{i+1}$ координатад огтлолцоно,

$$ - f(x_i) = f'(x_i)(x_{i+1} - x_i) $$

Одоо тэгшитгэлийг бодоод бид $x_{i+1}$-ийн утгыг олно.

Хэрэв $f(x)$ функц "сайн" (гөлгөр) бөгөөд $x_i$ нь язгуурт хангалттай ойр бол $x_{i+1}$ нь хайж буй язгуурт улам ойр байх нь зөн совингоор тодорхой.

Нийлэх хурд нь квадрат бөгөөд энэ нь болзолтойгоор хэлбэл $x_i$ ойролцоо утга дахь яг тоонуудын тоо итерац бүрд хоёр дахин нэмэгдэнэ гэсэн үг.

Квадрат язгуур тооцоолоход хэрэглэх нь

Ньютоны аргын жишээ болгон квадрат язгуур тооцоолохыг ашиглая.

Хэрэв бид $f(x) = x^2 - n$-г орлуулбал илэрхийллийг хялбарчилсны дараа бид:

$$ x_{i+1} = \frac{x_i + \frac{n}{x_i}}{2} $$

Бодлогын эхний ердийн хувилбар нь $n$ рационал тоо өгөгдсөн бөгөөд түүний язгуурыг ямар нэг eps нарийвчлалтайгаар тооцоолох ёстой үе юм:

double sqrt_newton(double n) {
    const double eps = 1E-15;
    double x = 1;
    for (;;) {
        double nx = (x + n / x) / 2;
        if (abs(x - nx) < eps)
            break;
        x = nx;
    }
    return x;
}

Бодлогын өөр нэг түгээмэл хувилбар нь бид бүхэл язгуурыг тооцоолох хэрэгтэй үе юм (өгөгдсөн $n$-ийн хувьд $x^2 \le n$ байх хамгийн их $x$-ийг ол). Энд алгоритмын зогсох нөхцөлийг бага зэрэг өөрчлөх шаардлагатай, учир нь $x$ хариуны ойролцоо "үсрэх" эхэлж болзошгүй. Тиймээс бид $x$ утга өмнөх алхамд буурсан бөгөөд одоогийн алхамд нэмэгдэхийг оролдож байвал алгоритмыг зогсоох ёстой гэсэн нөхцөл нэмнэ.

int isqrt_newton(int n) {
    int x = 1;
    bool decreased = false;
    for (;;) {
        int nx = (x + n / x) >> 1;
        if (x == nx || nx > x && decreased)
            break;
        decreased = nx < x;
        x = nx;
    }
    return x;
}

Эцэст нь бидэнд гурав дахь хувилбар өгөгдсөн — том тооны арифметикийн тохиолдол. $n$ тоо хангалттай том байж болох тул эхний ойролцооллд анхаарал хандуулах нь зүйтэй. Мэдээж энэ нь язгуурт ойр байх тусам үр дүнд хурдан хүрнэ. Эхний ойролцооллыг $2^{\textrm{bits}/2}$ тоо болгон авах нь хангалттай энгийн бөгөөд үр дүнтэй, энд $\textrm{bits}$ нь $n$ тоон дахь битийн тоо юм. Энэ хувилбарыг харуулсан Java код энд байна:

public static BigInteger isqrtNewton(BigInteger n) {
    BigInteger a = BigInteger.ONE.shiftLeft(n.bitLength() / 2);
    boolean p_dec = false;
    for (;;) {
        BigInteger b = n.divide(a).add(a).shiftRight(1);
        if (a.compareTo(b) == 0 || a.compareTo(b) < 0 && p_dec)
            break;
        p_dec = a.compareTo(b) > 0;
        a = b;
    }
    return a;
}

Жишээ нь энэ код $n = 10^{1000}$-ийн хувьд $60$ миллисекундэд ажиллах ба хэрэв бид эхний ойролцооллын сайжруулсан сонголтыг хасвал (зүгээр л $1$-ээс эхэлбэл) ойролцоогоор $120$ миллисекундэд ажиллана.

Дасгал бодлогууд