لن اضيع هذه النقطة الهامة او ربما الاهم فى المنطق و لا فى اللغة و لا فى منهج العقل و لا منهج السلف و لا فى منهج آل البيت...
سأستخدم الرياضيات من النوع الذى احب و الذى اثق فيه: الحساب القابل للتشفير..
مثال: كيف تقلب مصفوفة بالفعل دون ان تقلبها حقيقة!!!
لتكن $A$ مصفوفة موجبة و متناظرة بعدها $n$. وليكن $v$ شعاع ما. المطلوب هو ايجاد الشعاع $x$ الذى يحقق المعادلة
سأستخدم الرياضيات من النوع الذى احب و الذى اثق فيه: الحساب القابل للتشفير..
مثال: كيف تقلب مصفوفة بالفعل دون ان تقلبها حقيقة!!!
لتكن $A$ مصفوفة موجبة و متناظرة بعدها $n$. وليكن $v$ شعاع ما. المطلوب هو ايجاد الشعاع $x$ الذى يحقق المعادلة
\begin{equation}
A.x=v.
\end{equation}
الحل معروف يتطلب قلب المصفوفة A ويعطى ب
\begin{eqnarray}
x=A^{-1}v.
\end{eqnarray}
لكن قلب المصفوفات عمل معقد جدا من الناحية التحليلية و العددية و هو يكلف فى افضل الخواروزميات زمن متناسب مع
$n^3$
من اجل مصفوفة بعدها
$n$.
البديل هو طريقة التدريج المرافق
conjugate gradient method
التى سوف تعطى لنا الحل
$x$
وكأننا قلبنا المصفوفة $A$ بالفعل دون ان نحتاج ان نقلب حقيقة المصفوفة
$A$.
هذه الخوارزمية بدون برهان تعطى كالاتى:
- نختار نقطة انطلاق معينة $x_0$ كما نشاء.
- نحسب ما يسمى بالباقى فى هذه النقطة الذى يعطى بالعلاقة \begin{eqnarray} r_0=v-A.x_0.\nonumber \end{eqnarray} نختار اتجاه البحث الاول بالعلاقة \begin{eqnarray} p_1=r_0.\nonumber \end{eqnarray} الحل الاول يعطى اذن ب \begin{eqnarray} x_1=x_0+s_1.p_1,\nonumber \end{eqnarray} حيث ان المعامل $s_1$ يعطى ب \begin{eqnarray} s_1=\frac{p_1r_0}{p_1Ap_1}.\nonumber \end{eqnarray}
- نحسب الباقى الثانى و نختار اتجاه البحث الثانى بالعلاقتين \begin{eqnarray} r_1=v-A.x_1,\nonumber \end{eqnarray} و \begin{eqnarray} p_2=r_1-\lambda p_1,\nonumber \end{eqnarray} حيث ان المعامل $\lambda$ يعطى بالعلاقة \begin{eqnarray} \lambda=\frac{p_1Ar_1}{p_1Ap_1}.\nonumber \end{eqnarray} الحل الثانى يعطى اذن بالعلاقة \begin{eqnarray} x_2=x_1+s_2.p_2,\nonumber \end{eqnarray} حيث ان المعامل $s_2$ يعطى ب \begin{eqnarray} s_2=\frac{p_2r_1}{p_2Ap_2}.\nonumber \end{eqnarray}
- نكرر على كل اشعة البحث $p_i$ كما يلى \begin{eqnarray} r_i=v-A.x_i,\nonumber \end{eqnarray} \begin{eqnarray} p_{i+1}=r_i-\lambda p_i~,~\lambda=\frac{p_iAr_i}{p_iAp_i}.\nonumber \end{eqnarray} \begin{eqnarray} x_{i+1}=x_i+s_{i+1}.p_{i+1}~,~ s_{i+1}=\frac{p_{i+1}r_i}{p_{i+1}Ap_{i+1}}.\nonumber \end{eqnarray}
- نكرر حتى يقترب الحل المحصل عليه بهذه الطريقة من الحل الحقيقى بأى دقة نختارها. نحن نعرف اننا اقتربنا من الحل الحقيقى من مراقبة قيمة الباقى التى عندما تصغر بما فيه الكفاية يمكن ان نتوقف.
من المؤكد ان هذه الطريقة ستقترب من الحل و بسرعة كبيرة جدا. لكن لاحظ اننا لم نقلب حقيقة المصفوفة
$A$.
أما البرهان على كل هذا فيمكننى ان اعطيه لمن يسأل او لمن شك!!!...
وكما دائما اقول الفهم الحقيقى لا يتأتى الا بالبرهان الحقيقى....
هذا المثال هو من افضل ما اعرف عن الفرق بين ماهو واقع بالفعل -وكأننا قلبنا المصفوفة هنا- وما هو واقع فى الحقيقة -عدم قلبها حقيقة-..
فهناك فرق رهيب بين المستويين لا يدركه الا القلة من الفلاسفة و الرياضيين و الفيزيائيين النظريين...
the conjugate gradient method is an algorithm for the numerical solution of particular systems of linear equations, namely those whose matrix is symmetric and positive-definite. 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.
ReplyDeleteThe conjugate gradient method can also be used to solve unconstrained optimization problems such as energy minimization. It was mainly developed by Magnus Hestenes and Eduard Stiefel.[1]
The biconjugate gradient method provides a generalization to non-symmetric matrices. Various nonlinear conjugate gradient methods seek minima of nonlinear equations.
Example code in MATLAB / GNU Octave[edit]
function [x] = conjgrad(A, b, x)
r = b - A * x;
p = r;
rsold = r' * r;
for i = 1:length(b)
Ap = A * p;
alpha = rsold / (p' * Ap);
x = x + alpha * p;
r = r - alpha * Ap;
rsnew = r' * r;
if sqrt(rsnew) < 1e-10
break;
end
p = r + (rsnew / rsold) * p;
rsold = rsnew;
end
end