Conjugate gradient method
ગણિતમાં, કોન્જુગેટ ગ્રેડિયન્ટ પદ્ધતિ એ રેખીય સમીકરણોની ચોક્કસ પ્રણાલીઓના આંકડાકીય ઉકેલ માટે એક અલ્ગોરિધમ છે, એટલે કે જેની મેટ્રિક્સ હકારાત્મક-નિશ્ચિત છે. કોન્જ્યુગેટ ગ્રેડિયન્ટ પદ્ધતિ ઘણીવાર પુનરાવર્તિત અલ્ગોરિધમ તરીકે લાગુ કરવામાં આવે છે, જે વિરલ પ્રણાલીઓને લાગુ પડે છે જે સીધા અમલીકરણ અથવા અન્ય સીધી પદ્ધતિઓ જેમ કે કોલેસ્કી વિઘટન દ્વારા નિયંત્રિત કરવા માટે ખૂબ મોટી હોય છે. આંશિક વિભેદક સમીકરણો અથવા ઓપ્ટિમાઇઝેશન સમસ્યાઓને આંકડાકીય રીતે હલ કરતી વખતે ઘણીવાર મોટી વિરલ પ્રણાલીઓ ઊભી થાય છે. કન્જુગેટ ગ્રેડિયન્ટ પદ્ધતિનો ઉપયોગ ઊર્જા લઘુતમકરણ જેવી અનિયંત્રિત ઓપ્ટિમાઇઝેશન સમસ્યાઓને ઉકેલવા માટે પણ થઈ શકે છે. તે સામાન્ય રીતે મેગ્નસ હેસ્ટેન્સ અને એડવર્ડ સ્ટીફેલને આભારી છે, જેમણે તેને ઝેડ 4 પર પ્રોગ્રામ કર્યો હતો અને તેના પર વ્યાપક સંશોધન કર્યું હતું. બાયકોનજુગેટ ગ્રેડિયન્ટ પદ્ધતિ બિન-સમમિતીય મેટ્રિસીસને સામાન્યીકરણ પ્રદાન કરે છે. વિવિધ બિનરેખીય સંયુગ્મ ઢાળ પદ્ધતિઓ બિનરેખીય ઓપ્ટિમાઇઝેશન સમસ્યાઓની લઘુતમ શોધ કરે છે. સંયુગ્મ ઢાળ દ્વારા સંબોધવામાં આવેલી સમસ્યાનું વર્ણન ધારો કે આપણે વેક્ટર માટે રેખીય સમીકરણોની પ્રણાલીને ઉકેલવા માંગીએ છીએ, જ્યાં જાણીતું મેટ્રિક્સ સપ્રમાણ (એટલે કે, AT = A), હકારાત્મક-નિશ્ચિત (એટલે કે. Rn માં તમામ બિન-શૂન્ય વેક્ટર માટે xTAx> 0), અને વાસ્તવિક, અને તે પણ જાણીતું છે. અમે આ પ્રણાલીના અનન્ય ઉકેલને સૂચવીએ છીએ. સીધી પદ્ધતિ તરીકે વ્યુત્પત્તિ સંયુગ્મ ઢાળ પદ્ધતિ ઘણા જુદા જુદા પરિપ્રેક્ષ્યોમાંથી મેળવી શકાય છે, જેમાં ઓપ્ટિમાઇઝેશન માટે સંયુગ્મ દિશા પદ્ધતિની વિશેષતા અને આઈગનવેલ્યુ સમસ્યાઓ માટે આર્નોલ્ડી/લેન્ક્ઝોસ પુનરાવર્તનની વિવિધતા સામેલ છે. તેમના અભિગમોમાં તફાવતો હોવા છતાં, આ વ્યુત્પત્તિઓ એક સામાન્ય વિષય શેર કરે છે-અવશેષોની ઓર્થોગોનાલિટી અને શોધ દિશાઓની સંયોગને સાબિત કરે છે. આ બે ગુણધર્મો પદ્ધતિની જાણીતી સંક્ષિપ્ત રચના વિકસાવવા માટે નિર્ણાયક છે. આપણે કહીએ છીએ કે બે બિન-શૂન્ય વેક્ટર u અને v સંયુક્ત છે (સંદર્ભમાં) જો તે સપ્રમાણ અને હકારાત્મક-નિશ્ચિત હોય, તો ડાબી બાજુ આંતરિક ઉત્પાદનને વ્યાખ્યાયિત કરે છે બે વેક્ટર સંયુક્ત હોય છે જો અને માત્ર ત્યારે જ જો તેઓ આ આંતરિક ઉત્પાદનના સંદર્ભમાં ઓર્થોગોનલ હોય. સંયુગ્મ બનવું એ એક સપ્રમાણ સંબંધ છેઃ જો સંયુગ્મ હોય, તો તે સંયુગ્મ હોય છે. ધારો કે તે પરસ્પર સંયુગ્મિત વેક્ટરનો સમૂહ છે, એટલે કે. બધા માટે. પછી એક આધાર બનાવે છે, અને આપણે આ આધારમાં ઉકેલને વ્યક્ત કરી શકીએ છીએઃ વેક્ટર ઉપજ સાથે સમસ્યાને ડાબે ગુણાકાર કરવો અને તેથી આ સમીકરણને ઉકેલવા માટે નીચેની પદ્ધતિ આપે છેઃ સંયુગ્મિત દિશાઓનો ક્રમ શોધો, અને પછી ગુણાંકની ગણતરી કરો. પુનરાવર્તિત પદ્ધતિ તરીકે જો આપણે સંયુગ્મ વેક્ટરને કાળજીપૂર્વક પસંદ કરીએ, તો આપણને ઉકેલનો સારો અંદાજ મેળવવા માટે તે બધાની જરૂર નહીં પડે. તેથી, આપણે કોન્જ્યુગેટ ગ્રેડિયન્ટ પદ્ધતિને પુનરાવર્તિત પદ્ધતિ તરીકે ગણવા માંગીએ છીએ. આ આપણને લગભગ એવી પ્રણાલીઓને ઉકેલવા માટે પણ પરવાનગી આપે છે જ્યાં n એટલી મોટી છે કે સીધી પદ્ધતિમાં ઘણો સમય લાગશે. અમે બાય માટે પ્રારંભિક અનુમાન સૂચવીએ છીએ (આપણે સામાન્યતાને ગુમાવ્યા વિના ધારી શકીએ છીએ કે, અન્યથા તેના બદલે સિસ્ટમ એઝ = બી − એક્સ 0 ને ધ્યાનમાં લો). x0 થી શરૂ કરીને આપણે ઉકેલ શોધીએ છીએ અને દરેક પુનરાવર્તનમાં આપણને એ જણાવવા માટે મેટ્રિકની જરૂર પડે છે કે શું આપણે ઉકેલની નજીક છીએ (જે આપણને અજ્ઞાત છે). આ મેટ્રિક એ હકીકત પરથી આવે છે કે ઉકેલ પણ નીચેના વર્ગાત્મક વિધેયનો અનન્ય લઘુતમકર્તા છે એક અનન્ય લઘુતમકર્તાનું અસ્તિત્વ સ્પષ્ટ છે કારણ કે તેના બીજા વ્યુત્પન્નોનો હેસિયન મેટ્રિક્સ સપ્રમાણ હકારાત્મક-નિશ્ચિત છે અને લઘુતમકર્તા (Df (x) = 0 નો ઉપયોગ કરો) તેના પ્રથમ વ્યુત્પન્નથી અનુસરતી પ્રારંભિક સમસ્યાનું સમાધાન કરે છે. f નો ઢાળ બરાબર છે. પ્રારંભિક અનુમાન x0 થી શરૂ કરીને, આનો અર્થ એ છે કે આપણે p0 = b − Ax0 લઈએ છીએ. આધારમાંના અન્ય વેક્ટર ઢાળ સાથે સંયોજિત થશે, તેથી તેનું નામ સંયુગ્મિત ઢાળ પદ્ધતિ છે. નોંધ લો કે p0 એ અલ્ગોરિધમના આ પ્રારંભિક પગલા દ્વારા પ્રદાન કરાયેલ અવશેષ પણ છે. ધારો કે rk એ kમા પગલા પર અવશેષ છેઃ ઉપર અવલોકન કર્યા મુજબ, તે at નો નકારાત્મક ઢાળ છે, તેથી ઢાળ વંશ પદ્ધતિને rk દિશામાં ખસેડવાની જરૂર પડશે. અહીં, જો કે, અમે આગ્રહ રાખીએ છીએ કે દિશાઓ એકબીજા સાથે સંયોજિત હોવી જોઈએ. આને લાગુ કરવાની વ્યવહારુ રીત એ છે કે આગામી શોધ દિશા વર્તમાન અવશેષ અને અગાઉની તમામ શોધ દિશાઓમાંથી બનાવવામાં આવે. સંયુગ્મન અવરોધ એ ઓર્થોનોર્મલ-પ્રકારનો અવરોધ છે અને તેથી અલ્ગોરિધમને ગ્રામ-શ્મિટ ઓર્થોનોર્મલાઇઝેશનના ઉદાહરણ તરીકે જોઈ શકાય છે. આ નીચેની અભિવ્યક્તિ આપે છેઃ (અભિસરણ પર સંયોગની મર્યાદાની અસર માટે લેખની ટોચ પરનું ચિત્ર જુઓ). આ દિશાને અનુસરીને, આગામી શ્રેષ્ઠ સ્થાન દ્વારા આપવામાં આવે છે જ્યાં છેલ્લી સમાનતા ની વ્યાખ્યામાંથી અનુસરે છે. માટે અભિવ્યક્તિ મેળવી શકાય છે જો કોઈ xk + 1 માટે અભિવ્યક્તિને f માં બદલે છે અને તેને પરિણામી અલ્ગોરિધમનો સંદર્ભમાં ઘટાડે છે ઉપરોક્ત અલ્ગોરિધમ સંયુગ્મ ઢાળ પદ્ધતિની સૌથી સીધી સમજૂતી આપે છે. દેખીતી રીતે, જણાવ્યા મુજબ અલ્ગોરિધમને અગાઉની તમામ શોધ દિશાઓ અને અવશેષ વેક્ટર, તેમજ ઘણા મેટ્રિક્સ-વેક્ટર ગુણાકારોના સંગ્રહની જરૂર છે, અને તેથી તે ગણતરીત્મક રીતે ખર્ચાળ હોઈ શકે છે. જો કે, અલ્ગોરિધમનો નજીકથી વિશ્લેષણ દર્શાવે છે કે તે ઓર્થોગોનલ છે, એટલે કે. , i ષ્ણાંક j માટે. અને તે-ઓર્થોગોનલ છે, એટલે કે. માટે. આને ગણી શકાય કે જેમ જેમ અલ્ગોરિધમ પ્રગતિ કરે છે, અને તે જ ક્રાયલોવ સબસ્પેસનો વિસ્તાર કરે છે. જ્યાં પ્રમાણભૂત આંતરિક ઉત્પાદનના સંદર્ભમાં ઓર્થોગોનલ આધાર બનાવે છે, અને તેના દ્વારા પ્રેરિત આંતરિક ઉત્પાદનના સંદર્ભમાં ઓર્થોગોનલ આધાર બનાવે છે. તેથી, તેને ક્રાયલોવ સબસ્પેસ પરના પ્રક્ષેપણ તરીકે ગણી શકાય. Ax = b ને ઉકેલવા માટે અલ્ગોરિધમ નીચે વિગતવાર છે જ્યાં વાસ્તવિક, સપ્રમાણ, હકારાત્મક-નિશ્ચિત મેટ્રિક્સ છે. ઇનપુટ વેક્ટર અંદાજિત પ્રારંભિક ઉકેલ અથવા 0 હોઈ શકે છે. તે ઉપર વર્ણવેલ ચોક્કસ પ્રક્રિયાની એક અલગ રચના છે. આ સૌથી વધુ ઉપયોગમાં લેવાતું અલ્ગોરિધમ છે. આ જ સૂત્રનો ઉપયોગ ફ્લેચર-રીવ્સ બિનરેખીય સંયુગ્મ ઢાળ પદ્ધતિમાં પણ થાય છે. આપણે નોંધ્યું છે કે તેની ગણતરી ગ્રેડિયન્ટ ડિસેન્ટ પદ્ધતિ દ્વારા કરવામાં આવે છે. સેટિંગ એ જ રીતે ગ્રેડિયન્ટ ડિસેન્ટ પદ્ધતિ દ્વારા ગણતરી કરશે, એટલે કે, સંયુક્ત ગ્રેડિયન્ટ પુનરાવર્તનના પુનઃપ્રારંભના સરળ અમલીકરણ તરીકે ઉપયોગ કરી શકાય છે. પુનઃપ્રારંભ અભિસરણને ધીમું કરી શકે છે, પરંતુ જો સંયુક્ત ઢાળ પદ્ધતિ ખોટી વર્તણૂક કરે તો સ્થિરતામાં સુધારો થઈ શકે છે, દા. ત., રાઉન્ડ-ઓફ ભૂલને કારણે. સ્પષ્ટ શેષ ગણતરી સૂત્રો અને, જે બંને ચોક્કસ અંકગણિતમાં ધરાવે છે, તે સૂત્રો અને ગાણિતિક રીતે સમકક્ષ બનાવે છે. પહેલાનો ઉપયોગ અલ્ગોરિધમમાં વધારાના ગુણાકારને ટાળવા માટે થાય છે કારણ કે વેક્ટરનું મૂલ્યાંકન કરવા માટે પહેલેથી જ ગણતરી કરવામાં આવી છે. બાદમાં વધુ સચોટ હોઈ શકે છે, રાઉન્ડ-ઓફ ભૂલ સંચયને આધિન પુનરાવર્તન દ્વારા ગર્ભિત માટે સ્પષ્ટ ગણતરીને બદલીને, અને આમ પ્રસંગોપાત મૂલ્યાંકન માટે ભલામણ કરવામાં આવે છે. અવશેષના ધોરણનો ઉપયોગ સામાન્ય રીતે માપદંડ રોકવા માટે થાય છે. સ્પષ્ટ અવશેષનું ધોરણ ચોક્કસ અંકગણિત અને ગોળાકાર ભૂલોની હાજરીમાં ચોકસાઈનું બાંયધરીકૃત સ્તર પ્રદાન કરે છે, જ્યાં અભિસરણ કુદરતી રીતે સ્થિર થાય છે. તેનાથી વિપરીત, ગર્ભિત અવશેષ ગોળાકાર ભૂલોના સ્તરથી નીચે કંપનવિસ્તારમાં નાનું થતું રહે છે અને તેથી તેનો ઉપયોગ અભિસરણની સ્થિરતા નક્કી કરવા માટે કરી શકાતો નથી. આલ્ફા અને બીટાની ગણતરી અલ્ગોરિધમમાં, એવી રીતે પસંદ કરવામાં આવે છે કે જે ઓર્થોગોનલ હોય. ત્યારથી છેદને સરળ બનાવવામાં આવ્યો છે. પસંદ કરવામાં આવે છે જેમ કે સંયુગ્મિત છે. શરૂઆતમાં, ઉપયોગ કરી રહ્યું છે અને તેની સમકક્ષ અંશને કારણ તરીકે ફરીથી લખવામાં આવે છે અને ડિઝાઇન દ્વારા ઓર્થોગોનલ છે. છેદને એ રીતે ફરીથી લખવામાં આવે છે કે શોધ દિશાઓ pk સંયોજિત છે અને ફરીથી અવશેષો ઓર્થોગોનલ છે. આ રદ કર્યા પછી અલ્ગોરિધમમાં આપે છે. જુલિયા (પ્રોગ્રામિંગ ભાષા) માં ઉદાહરણ કોડ "" "કન્જ્યુગેટ _ ગ્રેડિયન્ટ! (A, b, x) સંયુગ્મ ઢાળ પદ્ધતિનો ઉપયોગ કરીને ઉકેલને 'A * x = b' પર પાછો લાવો. કાર્ય સંયોજીત કરો (_ g)! (A:: એબ્સ્ટ્રેક્ટમેટ્રિક્સ, b:: એબ્સ્ટ્રેક્ટવેક્ટર, x:: એબ્સ્ટ્રેક્ટવેક્ટર; tol = eps (eltype (b))) #અવશેષ વેક્ટર અવશેષને પ્રારંભ કરો = b-A * x #પ્રારંભિક શોધ દિશા વેક્ટર શોધ દિશા = શેષ #પ્રારંભિક વર્ગ અવશેષ ધોરણ જૂના _ sqr _ રેસિડ _ ધોરણ = શેષ '* અવશેષ #સંકલન સુધી પુનરાવર્તન કરો જ્યારે જૂના _ sqr _ રેસિડ _ ધોરણ> ટોલ A _ સર્ચ _ દિશા = A * શોધ _ દિશા પગલું _ કદ = જૂના _ sqr _ અવશેષ ધોરણ x = x + પગલું _ કદ * શોધ _ દિશા #શેષ @ને અપડેટ કરો. અવશેષ = શેષ-પગલું _ કદ * A _ શોધ _ દિશા નવા _ sqr _ અવશેષ _ ધોરણ = બિંદુ (શેષ, શેષ) #શોધ દિશા વેક્ટર @ને અપડેટ કરો. સર્ચ _ ડાયરેક્શન = રેસિડ્યુઅલ + (ન્યુ _ સ્ક્વેર _ રેસિડ _ નોર્મ/ઓલ્ડ _ સ્ક્વેર _ રેસિડ _ નોર્મ) ^ 2 * સર્ચ _ ડાયરેક્શન #આગામી પુનરાવર્તન જૂના _ સ્ક્વેર _ રેસિડ _ નોર્મ = ન્યુ _ સ્ક્વેર _ રેસિડ _ નોર્મ એન્ડ રીટર્ન x એન્ડ માટે સ્ક્વેર રેસિડ્યુઅલ નોર્મ અપડેટ કરો આંકડાકીય ઉદાહરણ લીનિયર સિસ્ટમ Ax = b દ્વારા આપવામાં આવેલ છે તે ધ્યાનમાં લો, આપણે સિસ્ટમનો અંદાજિત ઉકેલ શોધવા માટે પ્રારંભિક અનુમાનથી શરૂ કરીને કોન્જુગેટ ગ્રેડિયન્ટ પદ્ધતિના બે પગલાં લઈશું. ઉકેલ સંદર્ભ માટે, ચોક્કસ ઉકેલ એ છે કે આપણું પ્રથમ પગલું x0 સાથે સંકળાયેલ અવશેષ વેક્ટર r0 ની ગણતરી કરવાનું છે. આ અવશેષની ગણતરી r0 = b-Ax0 સૂત્રમાંથી કરવામાં આવે છે, અને આપણા કિસ્સામાં તે બરાબર છે કારણ કે આ પ્રથમ પુનરાવર્તન છે, તેથી આપણે અવશેષ વેક્ટર r0 નો ઉપયોગ આપણી પ્રારંભિક શોધ દિશા p0 તરીકે કરીશું; pk પસંદ કરવાની પદ્ધતિ આગળના પુનરાવર્તનોમાં બદલાશે. હવે આપણે સંબંધનો ઉપયોગ કરીને સ્કેલરની ગણતરી કરીએ છીએ આપણે હવે સૂત્રનો ઉપયોગ કરીને x1 ની ગણતરી કરી શકીએ છીએ આ પરિણામ પ્રથમ પુનરાવર્તન પૂર્ણ કરે છે, પરિણામ સિસ્ટમનો "સુધારેલ" અંદાજિત ઉકેલ છે, x1. હવે આપણે સૂત્રનો ઉપયોગ કરીને આગળ વધી શકીએ છીએ અને આગામી અવશેષ વેક્ટર r1 ની ગણતરી કરી શકીએ છીએ. આ પ્રક્રિયામાં આપણું આગળનું પગલું સ્કેલરની ગણતરી કરવાનું છે જેનો ઉપયોગ આખરે આગામી શોધ દિશા p1 નક્કી કરવા માટે કરવામાં આવશે. હવે, આ સ્કેલરનો ઉપયોગ કરીને, આપણે સંબંધનો ઉપયોગ કરીને આગામી શોધ દિશા p1 ની ગણતરી કરી શકીએ છીએ. છેવટે, આપણે x1 શોધવા માટે ઉપયોગમાં લેવાતી સમાન પદ્ધતિનો ઉપયોગ કરીને x2 શોધીએ છીએ. પરિણામ, x2, એ x1 અને x0 કરતાં સિસ્ટમના ઉકેલ માટે "વધુ સારું" અંદાજ છે. જો આ ઉદાહરણમાં મર્યાદિત-ચોકસાઈને બદલે ચોક્કસ અંકગણિતનો ઉપયોગ કરવામાં આવ્યો હોત, તો સૈદ્ધાંતિક રીતે ચોક્કસ ઉકેલ n = 2 પુનરાવર્તનો (n એ પ્રણાલીનો ક્રમ છે) પછી પહોંચી શકાયો હોત. કન્વર્જન્સ ગુણધર્મો કોન્જુગેટ ગ્રેડિયન્ટ પદ્ધતિને સૈદ્ધાંતિક રીતે સીધી પદ્ધતિ તરીકે જોઈ શકાય છે, કારણ કે રાઉન્ડ-ઓફ ભૂલની ગેરહાજરીમાં તે મર્યાદિત સંખ્યામાં પુનરાવર્તનો પછી ચોક્કસ ઉકેલ ઉત્પન્ન કરે છે, જે મેટ્રિક્સના કદ કરતા મોટો નથી. વ્યવહારમાં, ચોક્કસ ઉકેલ ક્યારેય પ્રાપ્ત થતો નથી કારણ કે સંયુગ્મ ઢાળ પદ્ધતિ નાના વિક્ષેપોના સંદર્ભમાં પણ અસ્થિર હોય છે, દા. ત., ક્રાયલોવ પેટા-જગ્યાઓ ઉત્પન્ન કરવાની ડીજનરેટિવ પ્રકૃતિને કારણે મોટાભાગની દિશાઓ વ્યવહારમાં સંયુગ્મ નથી. પુનરાવર્તિત પદ્ધતિ તરીકે, સંયુક્ત ઢાળ પદ્ધતિ એકવિધ રીતે (ઊર્જાના ધોરણમાં) ચોક્કસ ઉકેલના અંદાજમાં સુધારો કરે છે અને પુનરાવર્તનોની પ્રમાણમાં ઓછી (સમસ્યાના કદની સરખામણીમાં) સંખ્યા પછી જરૂરી સહનશીલતા સુધી પહોંચી શકે છે. સુધારો સામાન્ય રીતે રેખીય હોય છે અને તેની ઝડપ સિસ્ટમ મેટ્રિક્સની સ્થિતિ સંખ્યા દ્વારા નક્કી કરવામાં આવે છેઃ જેટલો મોટો હોય તેટલો સુધારો ધીમો હોય છે. જો તે મોટી હોય, તો પૂર્વશરતનો ઉપયોગ સામાન્ય રીતે મૂળ પ્રણાલીને તેના કરતા નાની સાથે બદલવા માટે થાય છે, નીચે જુઓ. કન્વર્જન્સ થીયરમ બહુપદીઓના સબસેટને વ્યાખ્યાયિત કરો કે જ્યાં મહત્તમ ડિગ્રીની બહુપદીઓનો સમૂહ છે. ચાલો ચોક્કસ ઉકેલના પુનરાવર્તિત અંદાજો હોઈએ, અને ભૂલોને આ રીતે વ્યાખ્યાયિત કરીએ. હવે, કન્વર્જન્સનો દર અંદાજિત કરી શકાય છે જ્યાં સ્પેક્ટ્રમ સૂચવે છે, અને કન્ડિશન નંબર સૂચવે છે. નોંધ લો, જ્યારે મહત્વપૂર્ણ મર્યાદા તરફ વલણ ધરાવે છે ત્યારે આ મર્યાદા જેકોબી અથવા ગૌસ-સીડેલની પુનરાવર્તિત પદ્ધતિઓની સરખામણીમાં ઝડપી અભિસરણ દર દર્શાવે છે. કન્વર્જન્સ થીયરમમાં કોઈ રાઉન્ડ-ઓફ ભૂલ ધારવામાં આવી નથી, પરંતુ કન્વર્જન્સ બાઉન્ડ સામાન્ય રીતે વ્યવહારમાં માન્ય છે, જેમ કે એન ગ્રીનબૌમ દ્વારા સૈદ્ધાંતિક રીતે સમજાવવામાં આવ્યું છે. વ્યવહારુ અભિસરણ જો અવ્યવસ્થિત રીતે પ્રારંભ કરવામાં આવે, તો પુનરાવર્તનનો પ્રથમ તબક્કો ઘણીવાર સૌથી ઝડપી હોય છે, કારણ કે ક્રાયલોવ સબસ્પેસમાં ભૂલ દૂર કરવામાં આવે છે જે શરૂઆતમાં નાની અસરકારક સ્થિતિ સંખ્યાને પ્રતિબિંબિત કરે છે. અભિસરણનો બીજો તબક્કો સામાન્ય રીતે તેની સાથે બંધાયેલા સૈદ્ધાંતિક અભિસરણ દ્વારા સારી રીતે વ્યાખ્યાયિત કરવામાં આવે છે, પરંતુ મેટ્રિક્સના વર્ણપટના વિતરણ અને ભૂલના વર્ણપટ વિતરણના આધારે તે અતિ-રેખીય હોઈ શકે છે. છેલ્લા તબક્કામાં, સૌથી નાની પ્રાપ્ય ચોકસાઈ સુધી પહોંચી શકાય છે અને કન્વર્જન્સ સ્ટોલ્સ અથવા પદ્ધતિ પણ અલગ થવાનું શરૂ કરી શકે છે. મોટા કદના મેટ્રિસીસ માટે ડબલ-પ્રિસિઝન ફ્લોટિંગ-પોઇન્ટ ફોર્મેટમાં લાક્ષણિક વૈજ્ઞાનિક કમ્પ્યુટિંગ એપ્લિકેશન્સમાં, કોન્જુગેટ ગ્રેડિયન્ટ પદ્ધતિ સહિષ્ણુતા સાથે સ્ટોપિંગ માપદંડનો ઉપયોગ કરે છે જે પ્રથમ અથવા બીજા તબક્કા દરમિયાન પુનરાવર્તનને સમાપ્ત કરે છે. પૂર્વશરત સંયુગ્મ ઢાળ પદ્ધતિ મોટાભાગના કિસ્સાઓમાં, સંયુગ્મ ઢાળ પદ્ધતિનું ઝડપી અભિસરણ સુનિશ્ચિત કરવા માટે પૂર્વશરત જરૂરી છે. જો સપ્રમાણ હકારાત્મક-નિશ્ચિત હોય અને તેના કરતાં વધુ સારી સ્થિતિ સંખ્યા હોય, તો પૂર્વશરત સંયુગ્મ ઢાળ પદ્ધતિનો ઉપયોગ કરી શકાય છે. તે નીચેનું સ્વરૂપ લે છેઃ પુનરાવર્તન કરો જો rk + 1 પૂરતા પ્રમાણમાં નાનું હોય તો બહાર નીકળો લૂપ સમાપ્ત થાય છે જો અંત પુનરાવર્તન કરે તો પરિણામ xk + 1 છે ઉપરોક્ત ફોર્મ્યુલેશન પૂર્વ-શરતી સિસ્ટમમાં નિયમિત સંયુગ્મિત ઢાળ પદ્ધતિ લાગુ કરવા સમાન છે જ્યાં સિસ્ટમની સમપ્રમાણતા (અને હકારાત્મક નિશ્ચિતતા) જાળવવા માટે પૂર્વ-શરતીના કોલેસ્કી વિઘટનનો ઉપયોગ કરવો આવશ્યક છે. જો કે, આ વિઘટનની ગણતરી કરવાની જરૂર નથી, અને તે જાણવું પૂરતું છે. તે બતાવી શકાય છે કે જે સમાન સ્પેક્ટ્રમ ધરાવે છે. પ્રી-કંડિશનર મેટ્રિક્સ M એ સપ્રમાણ હકારાત્મક-નિશ્ચિત અને નિશ્ચિત હોવું જોઈએ, એટલે કે, પુનરાવર્તનથી પુનરાવર્તનમાં બદલી શકાતું નથી. જો પૂર્વશરત પરની આમાંની કોઈપણ ધારણાઓનું ઉલ્લંઘન કરવામાં આવે, તો પૂર્વશરત સંયુગ્મ ઢાળ પદ્ધતિની વર્તણૂક અણધારી બની શકે છે. સામાન્ય રીતે ઉપયોગમાં લેવાતા પ્રી-કંડિશનરનું ઉદાહરણ અપૂર્ણ કોલેસ્કી ફેક્ટરાઇઝેશન છે. લવચીક પૂર્વશરત સંયુગ્મ ઢાળ પદ્ધતિ આંકડાકીય રીતે પડકારજનક એપ્લિકેશનોમાં, અત્યાધુનિક પૂર્વશરતોનો ઉપયોગ કરવામાં આવે છે, જે પરિવર્તનશીલ પૂર્વશરત તરફ દોરી શકે છે, પુનરાવર્તનો વચ્ચે બદલાઈ શકે છે. જો પૂર્વશરત દરેક પુનરાવર્તન પર સપ્રમાણ હકારાત્મક-નિશ્ચિત હોય તો પણ, તે બદલાઈ શકે છે તે હકીકત ઉપરની દલીલોને અમાન્ય બનાવે છે, અને વ્યવહારુ પરીક્ષણોમાં ઉપર પ્રસ્તુત અલ્ગોરિધમનો અભિસરણ નોંધપાત્ર રીતે ધીમું થાય છે. ફ્લેચર-રીવ્સ સૂત્રને બદલે પોલક-રિબિયર સૂત્રનો ઉપયોગ કરવાથી આ કિસ્સામાં અભિસરણમાં નાટ્યાત્મક રીતે સુધારો થઈ શકે છે. પૂર્વશરત સંયુગ્મ ઢાળ પદ્ધતિની આ આવૃત્તિને લવચીક કહી શકાય, કારણ કે તે ચલ પૂર્વશરત માટે પરવાનગી આપે છે. પૂર્વશરત સપ્રમાણ હકારાત્મક નિશ્ચિત (એસ. પી. ડી.) ન હોય તો પણ લવચીક સંસ્કરણ મજબૂત હોવાનું દર્શાવવામાં આવ્યું છે. લવચીક સંસ્કરણના અમલીકરણ માટે વધારાના વેક્ટરને સંગ્રહિત કરવાની જરૂર છે. નિશ્ચિત એસ. પી. ડી. પૂર્વશરત માટે, તેથી માટે બંને સૂત્રો ચોક્કસ અંકગણિતમાં સમકક્ષ છે, એટલે કે, રાઉન્ડ-ઓફ ભૂલ વિના. પોલક-રિબિયર સૂત્ર સાથે પદ્ધતિની વધુ સારી અભિસરણ વર્તણૂકનું ગાણિતિક સમજૂતી એ છે કે આ કિસ્સામાં પદ્ધતિ સ્થાનિક રીતે શ્રેષ્ઠ છે, ખાસ કરીને, તે સ્થાનિક રીતે શ્રેષ્ઠ સ્ટીપેસ્ટ ડિસેન્ટ પદ્ધતિ કરતાં ધીમી ગતિએ એકરૂપ થતી નથી. વિ. સ્થાનિક રીતે શ્રેષ્ઠ સ્ટીપેસ્ટ ડિસેન્ટ પદ્ધતિ મૂળ અને પૂર્વ-શરતી બંને સંયુગ્મિત ઢાળ પદ્ધતિઓમાં, લાઇન સર્ચ, સ્ટીપેસ્ટ ડિસેન્ટ પદ્ધતિઓનો ઉપયોગ કરીને, તેમને સ્થાનિક રીતે શ્રેષ્ઠ બનાવવા માટે માત્ર સેટ કરવાની જરૂર છે. આ અવેજી સાથે, વેક્ટર હંમેશા વેક્ટર જેવા જ હોય છે, તેથી વેક્ટરને સંગ્રહિત કરવાની જરૂર નથી. આમ, આ સૌથી તીવ્ર ઉતરતી પદ્ધતિઓનું દરેક પુનરાવર્તન સંયુગ્મિત ઢાળ પદ્ધતિઓની સરખામણીમાં થોડું સસ્તું છે. જો કે, જ્યાં સુધી (અત્યંત) ચલ અને/અથવા બિન-એસ. પી. ડી. પૂર્વશરતનો ઉપયોગ કરવામાં ન આવે ત્યાં સુધી બાદમાં ઝડપથી ભેગા થાય છે, ઉપર જુઓ. ડબલ ઇન્ટિગ્રેટર માટે ઓપ્ટિમલ ફીડબેક કંટ્રોલર તરીકે કોન્જુગેટ ગ્રેડિયન્ટ પદ્ધતિ કન્જુગેટ ગ્રેડિયન્ટ પદ્ધતિ પણ ઓપ્ટિમલ કંટ્રોલ થિયરીનો ઉપયોગ કરીને મેળવી શકાય છે. આ અભિગમમાં, કન્જુગેટ ગ્રેડિયન્ટ પદ્ધતિ શ્રેષ્ઠ પ્રતિસાદ નિયંત્રક તરીકે બહાર આવે છે, ડબલ ઇન્ટિગ્રેટર સિસ્ટમ માટે, જથ્થા અને ચલ પ્રતિસાદ લાભ છે. સામાન્ય સમીકરણો પર સંયુગ્મિત ઢાળ સંયુગ્મિત ઢાળ પદ્ધતિને સામાન્ય સમીકરણો ATA અને જમણી બાજુના વેક્ટર ATb પર લાગુ કરીને મનસ્વી n-by-m મેટ્રિક્સ પર લાગુ કરી શકાય છે, કારણ કે ATA એ કોઈપણ A માટે સપ્રમાણ હકારાત્મક-અર્ધ-પરિમિત મેટ્રિક્સ છે. પરિણામ સામાન્ય સમીકરણો (CGNR) પર સંયુક્ત ઢાળ છે. ATAx = ATb એક પુનરાવર્તિત પદ્ધતિ તરીકે, મેમરીમાં સ્પષ્ટપણે ATA રચવું જરૂરી નથી પરંતુ માત્ર મેટ્રિક્સ-વેક્ટર કરવા અને મેટ્રિક્સ-વેક્ટર ગુણાકારને સ્થાનાંતરિત કરવા માટે જરૂરી છે. તેથી, જ્યારે A એક વિરલ મેટ્રિક્સ હોય ત્યારે CGNR ખાસ કરીને ઉપયોગી છે કારણ કે આ કામગીરીઓ સામાન્ય રીતે અત્યંત કાર્યક્ષમ હોય છે. જો કે સામાન્ય સમીકરણો રચવાની નકારાત્મક બાજુ એ છે કે શરત સંખ્યા κ (ATA) એ κ2 (A) ની બરાબર છે અને તેથી CGNR ના અભિસરણનો દર ધીમો હોઈ શકે છે અને અંદાજિત ઉકેલની ગુણવત્તા રાઉન્ડઓફ ભૂલો માટે સંવેદનશીલ હોઈ શકે છે. સારી પૂર્વશરત શોધવી એ ઘણીવાર CGNR પદ્ધતિનો ઉપયોગ કરવાનો એક મહત્વપૂર્ણ ભાગ છે. કેટલાક અલ્ગોરિધમ્સ પ્રસ્તાવિત કરવામાં આવ્યા છે (દા. ત., CGLS, LSQR). એલએસક્યુઆર અલ્ગોરિધમ કથિત રીતે શ્રેષ્ઠ આંકડાકીય સ્થિરતા ધરાવે છે જ્યારે એ ખરાબ સ્થિતિમાં હોય, એટલે કે, એ પાસે મોટી સ્થિતિ સંખ્યા હોય છે. જટિલ હર્મિશિયન મેટ્રિક્સ માટે કોન્જુગેટ ગ્રેડિયન્ટ પદ્ધતિ કોમ્પ્લેક્સ-વેલ્યુડ મેટ્રિક્સ A અને વેક્ટર b, કોમ્પ્લેક્સ-વેલ્યુડ વેક્ટર x માટે રેખીય સમીકરણોની પદ્ધતિ, જ્યાં A એ હર્મિશિયન (એટલે કે, A '= A) અને પોઝિટિવ-ડેફિનિટ મેટ્રિક્સ છે, અને પ્રતીક' કોન્જુગેટ ટ્રાન્સપોઝને સૂચવે છે. તુચ્છ ફેરફાર ફક્ત દરેક જગ્યાએ વાસ્તવિક ટ્રાન્સપોઝ માટે કોન્જુગેટ ટ્રાન્સપોઝને બદલવાનો છે. બાયકોનજુગેટ ગ્રેડિયન્ટ મેથડ (BiCG) કોન્જ્યુગેટ ગ્રેડિયન્ટ સ્ક્વેર્ડ મેથડ (CGS) કોન્જ્યુગેટ રેસિડ્યુઅલ મેથડ ગૌસીયન બિલીફ પ્રોપાગેશન ઇટરેટિવ મેથડઃ લીનિયર સિસ્ટમ્સ ક્રાયલોવ સબસ્પેસ નોનલીનિયર કોન્જ્યુગેટ ગ્રેડિયન્ટ મેથડ પ્રી-કન્ડિશનિંગ સ્પાર્સ મેટ્રિક્સ-વેક્ટર ગુણાકાર સંદર્ભો વધુ વાંચન ગેરાર્ડ મ્યુરન્ટઃ "કોન્જ્યુગેટ ગ્રેડિયન્ટ અલ્ગોરિધમમાં સાયલન્ટ ભૂલોની શોધ અને સુધારણા", ન્યુમેરિકલ એલ્ગોરિધમ્સ, vol.92 (2023), pp.869-891. યુઆરએલ = https://doi.org/10.1007/s11075-022-01380-1 બાહ્ય કડીઓ આંકડાકીય રેખીય બીજગણિત ઢાળ પદ્ધતિઓ ઉદાહરણ તરીકે MATLAB/ઓક્ટેવ કોડ સાથેના લેખો