हिल्बर्ट मैट्रिक्स

Question

के साथ एक रैखिक प्रणाली के समाधान को खोजने का सबसे तेज वंशज मैं 5125 हिल्बर्ट मैट्रिक्स के साथ एक रैखिक प्रणाली के समाधान को समझने के लिए सबसे तेज मूल की विधि का उपयोग कर रहा हूं। मेरा मानना ​​है कि कोड इस संबंध में ठीक है कि यह मुझे सही जवाब देता है। मुझे लगता है कि

1. यह भी कई पुनरावृत्तियों ले जा रहा है सही जवाब पाने के लिए:

   मेरे समस्या यह है कि है। मेरा मानना ​​है कि मैंने एल्गोरिदम में कुछ याद किया होगा लेकिन मुझे यकीन नहीं है कि इस बिंदु पर क्या है।

2. मुझे यकीन नहीं है कि यह एल्गोरिदम लागू करने का सबसे प्रभावी तरीका है और इसके अतिरिक्त, यह थोड़ा उलझन में है जिस पर "tol" चुनना है।

इन पर कोई अंतर्दृष्टि की सराहना की जाएगी (विशेष रूप से 1.)। धन्यवाद!

% Method of Steepest Descent with tol 10^-6 
h = hilb(5);       %Hilbert 5x5 matrix 
b = [1;1;1;1;1];      %solution matrix 
solution = zeros(d,1);     %Initialization 
residual = h*solution - b; 
tol = 10^(-6) 
count = 0; 

while residual'*residual > tol; 
    roe = (residual'*residual)/(residual'*h*residual); 
    solution = solution - roe*residual; 
    residual = h*solution - b; 
    count = count + 1; 
end 

count 
solution 


%Method of Steepest Descent with tol 10^-12 
solution = zeros(d,1); 
residual = h*solution - b; 
tol = 10^(-12) 
count = 0; 

while residual'*residual > tol; 
    roe = (residual'*residual)/(residual'*h*residual); 
    solution = solution - roe*residual; 
    residual = residual - roe*h*residual; 
    count = count + 1; 
end 

count 
solution 

%another_solution = invhilb(5)*b   %Check for solution 

Answer 1

मैं ज्ञान एक गणितीय पहलू से आपकी समस्या से निपटने के लिए नहीं है, लेकिन देखने के एक प्रोग्रामिंग बिंदु से एक बिंदु मैं ध्यान दें सकता है।

वास्तव में आप सही हैं। यह परिणाम के लिए भी कई पुनरावृत्तियों ले जा रहा है जब तक यह हो जाता है:

Elapsed time is 6.487824 seconds. 

count = 

     292945 

जब आप एक अंतिम परिणाम के पास जाने के लिए एक कदम आकार को परिभाषित, कदम लंबाई अनुकूलित किया जाना है। अन्यथा आप उत्तर के करीब आने में बहुत धीमी हैं या आप कई बार इष्टतम उत्तर से गुज़र रहे हैं और इसके चारों ओर एक ज़िगज़ैग बना रहे हैं क्योंकि आपकी चरण की लंबाई बहुत बड़ी है।

कदम आकार का अनुकूलन करने के लिए, मैं पहली बार अपनी स्क्रिप्ट के अनुसार एक समारोह के रूप में (प्लस छोटे-मोटे संशोधन):

function [solution, count, T] = SDhilb(d, step) 
h = hilb(d); 
tic 
b = ones(d, 1); 
solution = zeros(d, 1); 
residual = h * solution - b; 
res2 = residual' * residual; 
tol = 10^(-6); 
count = 0; 
while res2 > tol; 
    roe = res2/(residual' * h * residual); 
    solution = solution - step * roe * residual; % here the step size appears 
    residual = h * solution - b; 
    count = count + 1; 
    res2 = residual' * residual; % let's calculate this once per iteration 
end 
T = toc; 

अब कदम आकार की एक सीमा (0.1: 0.1: 1.3) के लिए इस समारोह का उपयोग कर और हिल्बर्ट मैट्रिक्स की जोड़ी (घ = 2, 3, 4, 5) यह स्पष्ट है कि 1 एक कुशल कदम आकार नहीं है:

इसके बजाय, step = 0.9 और अधिक कुशल हो रहा है। देखें कि कुशल यह hilb(5) के मामले में है करते हैं:

[result, count, T] = SDhilb(5, 0.9) 

result = 

    3.1894 
    -85.7689 
    481.4906 
-894.8742 
    519.5830 


count = 

     1633 


T = 

    0.0204 

परिमाण के दो से अधिक आदेश है कौन सा तेजी से।

इसी प्रकार आप tol के विभिन्न मानों को आजमा सकते हैं यह देखने के लिए कि गति कितनी नाटकीय हो सकती है। उस स्थिति में कोई इष्टतम मूल्य नहीं है: सहनशीलता जितनी छोटी होगी, उतनी ही अधिक समय आपको प्रतीक्षा करने की आवश्यकता होगी।

Answer 2

ऐसा लगता है कि आपने एल्गोरिदम सही ढंग से लागू किया है (एक उत्तल वर्ग-कार्य को कम करने के लिए सटीक रेखा-खोज के साथ सबसे तेज मूल/ढाल वंश)।

कन्वर्जेंस धीमी है क्योंकि समस्या बीमार वातानुकूलित है: हिल्बर्ट मैट्रिक्स आप समझते हैं एक शर्त संख्या के ऊपर 400000. ढाल वंश धीमा हो जब समस्या बीमार वातानुकूलित है जाना जाता है है।

इसके बजाय एक अच्छी तरह से वातानुकूलित समस्या को ध्यान में रखते हुए, उदाहरण के लिए हिल्बर्ट मैट्रिक्स (एच = हिल्ब (5) + आंख (5)) में पहचान जोड़कर, वही कोड केवल 7 पुनरावृत्तियों के बाद समाप्त हो जाता है (और इसके लिए स्थिति संख्या वह मैट्रिक्स 3 से कम है)।