Кіріспе
Функцияның тұрақты нүктелерін табу әдісі
Есептеуде Ньютон әдісі (Ньютон-Рафсон әдісі деп те аталады) – дифференциалданатын F функциясының түбірлерін табуға арналған итеративтік әдіс, олар теңдеудің шешімдері болып табылады. Осылайша, Ньютон әдісі екі рет дифференциалданатын функцияның f’ туындысына қолданылып, туындының түбірлерін (яғни, f’ = 0 теңдеуінің шешімдерін) табуға болады, бұл f функциясының сындық нүктелері деп аталады. Бұл шешімдер минимумдар, максимумдар немесе шегініс нүктелері болуы мүмкін; толығырақ "Сындық нүкте (математика)" мақаласының "Көп айнымалылы" бөлімін және осы мақаланың "Геометриялық түсіндірме" бөлімін қараңыз. Бұл f функциясының (жалпы) минимумдарын табуға бағытталған оптимизацияда маңызды.
Геометриялық түсіндіру
Ньютон әдісінің геометриялық тұрғыдан түсіндірмесі – әрбір итерацияда бұл функцияның графигіне, сынақ мәніндегі нүктедегі графикпен бірдей еңіс және қисықтыққа ие параболаны сәйкестендіруге тең, содан кейін осы параболаның максимум немесе минимум нүктесіне көшу (жоғары өлшемдерде бұл сідірлік нүкте де болуы мүмкін), төменде қараңыз. Егер функция квадраттық болса, онда нақты экстремум бір қадамда табылады.
Ынтымақтастық
Егер f Липшиц Гессианы бар қатты дөңес функция болса, онда бастапқы шамасы жеткілікті жақын болған жағдайда, Ньютон әдісімен құрылған тізбек квадратикалық жылдамдықпен f функциясының (қажетті түрде бірегей) минимум нүктесіне жуықсады. Яғни,
Ньютон бағытын есептеу
Ньютон бағытын есептеу үшін жоғары өлшемдегі Гессиан матрицасының керісін табудың өте қымбат операция болуы мүмкін. Мұндай жағдайларда, Гессианды тікелей керіте берудің орнына, векторды сызықтық теңдеулер жүйесінің шешімі ретінде есептеу оңтайлырақ, оны әртүрлі факторлау арқылы немесе жуықтап (бірақ жоғары дәлдікпен) итеративтік әдістерді қолдану арқылы шешуге болады. Осы әдістердің көпшілігі тек белгілі бір теңдеулерге ғана қолданылады, мысалы, Чолски факторлауы және конъюгатты градиент әдісі тек Гессиан оң анықталған матрица болған жағдайда ғана жұмыс істейді. Бұл шектеу сияқты көрінсе де, көбінесе қателіктердің пайдалы индикаторы болып табылады; мысалы, егер минималдау мәселесі шешілсе және Гессиан оң анықталмаған болса, онда итерациялар минимумға емес, сідік нүктесіне жинақталады. Екінші жағынан, егер шектеулі оптимизация орындалса (мысалы, Лагранж көбейткіштерімен), мәселе сідік нүктесін табуға айналуы мүмкін, онда Гессиан симметриялық және анықталмаған болады, ал жүйенің шешімі осындай жағдайларда жұмыс істейтін әдіспен, мысалы, Чолски факторлауының модификациясы немесе конъюгатты қалдық әдісі арқылы табылуы керек. Гессианның (немесе оның керісінің) градиент өзгерулерінен құралатын квази-Ньютон әдістері де бар. Егер Гессиан инвертіленбейтін матрицаға жақын болса, инвертіленген Гессиан сандық тұрақсыз болуы мүмкін және шешім дивергенцияға ұшырауы мүмкін. Мұндай жағдайларда, бұрыннан белгілі бір тәсілдер қолданылған, олардың кейбір мәселелерде әртүрлі нәтижелер бергені байқалған. Мысалы, Гессианды оң анықталған ету үшін түзету матрицасын қосу арқылы өзгертуге болады. Бір тәсіл – Гессианды диагональдау және түзету матрицасын Гессианмен бірдей өзіндік векторларға ие болуы үшін таңдау, бірақ әрбір теріс өзіндік мәнін оң мәнмен алмастыру. Левенберг-Маркардт алгоритмінде (шамамен Гессианды қолданатын) Гессианға масштабталған бірлік матрицасын қосу тәсілі қолданылады, мұнда масштаб әр итерацияда қажеттікке қарай реттеледі. Үлкен және кішкентай Гессиан үшін итерациялар қадам өлшемімен градиенттік түсу сияқты әрекет етеді. Бұл Гессиан пайдалы ақпаратты бермейтін жағдайда, бірақ сенімді конвергенцияны қамтамасыз етеді.
which may be solved by various factorizations or approximately (but to great accuracy) using iterative methods. Many of these methods are only applicable to certain types of equations, for example the Cholesky factorization and conjugate gradient will only work if is a positive definite matrix. While this may seem like a limitation, it is often a useful indicator of something gone wrong; for example if a minimization problem is being approached and is not positive definite, then the iterations are converging to a saddle point and not a minimum. On the other hand, if a constrained optimization is done (for example, with Lagrange multipliers), the problem may become one of saddle point finding, in which case the Hessian will be symmetric indefinite and the solution of will need to be done with a method that will work for such, such as the variant of Cholesky factorization or the conjugate residual method. There also exist various quasi Newton methods, where an approximation for the Hessian (or its inverse directly) is built up from changes in the gradient. If the Hessian is close to a non invertible matrix, the inverted Hessian can be numerically unstable and the solution may diverge. In this case, certain workarounds have been tried in the past, which have varied success with certain problems. One can, for example, modify the Hessian by adding a correction matrix so as to make positive definite. One approach is to diagonalize the Hessian and choose so that has the same eigenvectors as the Hessian, but with each negative eigenvalue replaced by
An approach exploited in the Levenberg–Marquardt algorithm (which uses an approximate Hessian) is to add a scaled identity matrix to the Hessian, , with the scale adjusted at every iteration as needed. For large and small Hessian, the iterations will behave like gradient descent with step size This results in slower but more reliable convergence where the Hessian doesn't provide useful information.