Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Математикалық оңтайландыру алгоритмі
Mathematical optimization algorithm
Математикада конъюгатты градиент әдісі – белгілі бір сызықтық теңдеулер жүйесін сандық түрде шешуге арналған алгоритм, атап айтқанда, матрицасы оң жартылай белгілі болатын жүйелер үшін. Конъюгатты градиент әдісі көбінесе итеративтік алгоритм ретінде іске асырылады, ол тікелей есептеулермен немесе Чолески ыдырауы сияқты басқа тікелей әдістермен шешуге тым үлкен болатын сирек жүйелерге қолданылады. Үлкен сирек жүйелер көбінесе дербес дифференциалдық теңдеулерді немесе оңтайландыру мәселелерін сандық түрде шешу кезінде туындайды. Конъюгатты градиент әдісі энергияны азайту сияқты шектеусіз оңтайландыру мәселелерін шешу үшін де қолданылуы мүмкін. Бұл әдіс Магнус Хестенес пен Эдуард Стифельге жатқызылады, олар оны Z4 компьютерінде бағдарламалап, жан-жақты зерттеген. Биконъюгатты градиент әдісі симметриялық емес матрицалар үшін жалпылауды ұсынады. Әртүрлі сызықтық емес конъюгатты градиент әдістері сызықтық емес оңтайландыру мәселелерінің минимумдарын табуға бағытталған.
In mathematics, the conjugate gradient method is an algorithm for the numerical solution of particular systems of linear equations, namely those whose matrix is positive semidefinite. The conjugate gradient method is often implemented as an iterative algorithm, applicable to sparse systems that are too large to be handled by a direct implementation or other direct methods such as the Cholesky decomposition. Large sparse systems often arise when numerically solving partial differential equations or optimization problems. The conjugate gradient method can also be used to solve unconstrained optimization problems such as energy minimization. It is commonly attributed to Magnus Hestenes and Eduard Stiefel, who programmed it on the Z4, and extensively researched it. The biconjugate gradient method provides a generalization to non symmetric matrices. Various nonlinear conjugate gradient methods seek minima of nonlinear optimization problems.
Қайта бастау
Біз, егер градиенттік төмен түсу әдісі қолданылса, есептелетінін атап өтеміз. Сол сияқты, егер орнатылса, онда да градиенттік төмен түсу әдісі арқылы есептелер еді, яғни конъюгат градиент қайталауларын қайта бастаудың қарапайым іске асырылуы ретінде пайдаланылуы мүмкін. Қалдық нормасы әдетте тоқтату критерийлері үшін қолданылады. Нақты арифметикада да, дөңгелектеу қателері болған жағдайда да, қалдық нормасы конвергенция табиғи түрде тоқтағанда дәлдік деңгейін кепілдендіреді. Керісінше, имплицитті қалдық амплитудасы дөңгелектеу қателері деңгейінен әлдеқайда төмендеп, сондықтан конвергенцияның тоқтауын анықтау үшін қолданыла алмайды.
We note that is computed by the gradient descent method applied to Setting would similarly make computed by the gradient descent method from , i. e., can be used as a simple implementation of a restart of the conjugate gradient iterations. A norm of the residual is typically used for stopping criteria. The norm of the explicit residual provides a guaranteed level of accuracy both in exact arithmetic and in the presence of the rounding errors, where convergence naturally stagnates. In contrast, the implicit residual is known to keep getting smaller in amplitude well below the level of rounding errors and thus cannot be used to determine the stagnation of convergence.
Конвергенция қасиеттері
Конъюгатты градиент әдісін теориялық тұрғыдан тікелей әдіс ретінде қарастыруға болады, себебі дөңгелектеу қатесі болмаған жағдайда, ол шекті сандағы итерациялардан кейін нақты шешімді шығарады, бұл сан матрицаның өлшемінен аспайды. Бірақ іс жүзінде нақты шешімге жете алмаймыз, өйткені конъюгатты градиент әдісі тіпті кішкентай бұрмалауларға да сезімтал, мысалы, көптеген бағыттар іс жүзінде конъюгатты болмайды, себебі Крылов кеңістіктерін құру процесінің дегенеративті сипаты бар. Итеративтік әдіс ретінде, конъюгатты градиент әдісі нақты шешімге жуықтауды монотонды түрде (энергиялық нормада) жақсартады және салыстырмалы түрде аз (мәселенің көлеміне қарағанда) итерациядан кейін қажетті дәлдікке жете алады. Жақсарту әдетте сызықтық және оның жылдамдығы жүйелік матрицаның шартты санымен анықталады: шартты саны неғұрлым үлкен болса, жақсарту соғұрлым баяу болады. Егер шартты саны үлкен болса, бастапқы жүйені ауыстыру үшін алдын ала шарттау қолданылады, яғни -ты -мен алмастырады, мұндағы -ның мәні -дан кіші болады, қараңыз төменде.
The conjugate gradient method can theoretically be viewed as a direct method, as in the absence of round off error it produces the exact solution after a finite number of iterations, which is not larger than the size of the matrix. In practice, the exact solution is never obtained since the conjugate gradient method is unstable with respect to even small perturbations, e. g., most directions are not in practice conjugate, due to a degenerative nature of generating the Krylov subspaces. As an iterative method, the conjugate gradient method monotonically (in the energy norm) improves approximations to the exact solution and may reach the required tolerance after a relatively small (compared to the problem size) number of iterations. The improvement is typically linear and its speed is determined by the condition number of the system matrix : the larger is, the slower the improvement. If is large, preconditioning is commonly used to replace the original system with such that is smaller than , see below.
Жергілікті оптималдық ең тік түсу әдісімен салыстырғанда
Бастапқы және алдын ала шартталған конъюгат градиент әдістерінде оларды жергілікті түрде оптималды ету үшін сызықтық іздеу және ең тік түсу әдістерін қолдану үшін ғана орнату қажет. Осылайша, "p" векторлары әрқашан "z" векторларымен сәйкес келеді, сондықтан "p" векторларын сақтау қажет емес. Осының нәтижесінде, осы ең тік түсу әдістерінің әрбір итерациясы конъюгат градиент әдістеріне қарағанда аз шығынды болады. Дегенмен, соңғылары (қатты) өзгермелі немесе SPD емес алдын ала шарттауыш қолданылмаса, одан тез жинақталады, жоғарыда көрсетілгендей.
In both the original and the preconditioned conjugate gradient methods one only needs to set in order to make them locally optimal, using the line search, steepest descent methods. With this substitution, vectors 'p' are always the same as vectors 'z', so there is no need to store vectors 'p'. Thus, every iteration of these steepest descent methods is a bit cheaper compared to that for the conjugate gradient methods. However, the latter converge faster, unless a (highly) variable and/or non SPD preconditioner is used, see above.
Қосарланған градиент әдісі қос интегратор үшін оңтайлы кері байланыс контроллері ретінде
Конъюгатты градиент әдісін оптималды басқару теориясын қолдану арқылы да шығаруға болады. Бұл тәсілде конъюгатты градиент әдісі қос интегратор жүйесі үшін оңтайлы кері байланыс басқарушысы ретінде көрінеді, ал шамалар – өзгермелі кері байланыс коэффициенттері болып табылады.
The conjugate gradient method can also be derived using optimal control theory. In this approach, the conjugate gradient method falls out as an optimal feedback controller, for the double integrator system, The quantities and are variable feedback gains.