قاعده کرامر

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

در جبر خطی، قاعده کرامر روشی صریحی برای حل دستگاه معادلات خطی ای که تعداد معادلات با تعداد مجهولات برابر و دستگاه جواب منحصر بفرد دارد، است. این روش از دترمینان های ماتریس (مربع) ضرایب و ماتریس هایی که از جایگذاری یکی از ستون های ماتریس ضرایب با بردار سمت راست معادله بدست می آید، تعریف می گردد. این روش به نام گابریل کرامر (1704-1752) که این روش را برای تعداد دلخواهی از مجهولات در سال 1750 منتشر کرد[۱].اگرچه کولین مک‌لورین نیز در سال 1748 برای موارد خاص این روش را منتشر کرده بود [۲] (و احتمالاً در 1729 نیز این روش شناخته شده بود).[۳][۴][۵]

حالت کلی[ویرایش]

دستگاهی با n معادله و n مجهول را نظر بگیرید، که بشکل ماتریسی زیر قابل نمایش است:

 Ax = b\,
(1)\,

که در آن ماتریس A، n در n و دترمینانش مخالف صفر و بردار  x = (x_1, \ldots, x_n)^\mathrm{T} بردار ستونی متغیر ها است.

قضیه بیان می کند که در این حالت معادله جواب منحصر بفردی دارد، که مقدار متغیر هایش از رابطه زیر بدست می آید:

 x_i = \frac{\det(A_i)}{\det(A)} \qquad i = 1, \ldots, n \,

که در آن  A_i ماتریس حاصل از جایگذاری بردار ستونی b در ستون iام  A می باشد.

قائده کرامر برای معادلات با ضرایت و مجهولات تنها برایاعداد حقیقی نیست و برای هرمیدان تعریف می گردد. اخیراً نشان داده شده است که قائده کرامر را می توان در زمان  O( n^3 ) پیاده سازی کرد[۶]، که قابل مقایسه با سایر روش های رایج برای حل دستگاه معادلات خطی مانند روش حذفی گاوسی می باشد.

اثبات[ویرایش]

می دانیم که  \det(A) \neq 0 پس بنا به خواص دترمینان، ماتریس A معکوس دارد. از معکوس داشتن A نتیجه می گیریم که معادله  Ax = b جواب منحصر بفرد  A^{-1}b را دارد.( A(A^{-1} b) = (AA^{-1})b = b )

برای هر عدد صحیح i,1\leq i \leq n a_i را ستون iام ماتریس A و e_i را ستون i ام ماتریس همانی I_n درنظر بگیرید و X_i را ماریسی که از جایگذاری بردار ستونی X در ستون iام ماتریس همانی بدست می آید، در نظر بگیرید.

می دانیم ستون kام حاصل ضرب  AB برای هر ماتریس  A,B ، از ضرب ماتریس A در ستون kام ماتریس  B بدست می آید. پس بطور مشابه بدست می آید  Ae_k = a_k بازای  k = 1, \ldots ,n. بنابراین خواهیم داشت:

 \begin{array}{lll}
   AX_i & = & A (e_1,\ldots,e_{i-1},x,e_{i+1},\ldots,e_n) \\
        & = & (Ae_1,\ldots,Ae_{i-1},Ax,Ae_{i+1},\ldots,Ae_n) \\
        & = & (a_1,\ldots,a_{i-1},b,a_{i+1},\ldots,a_n) \\
        & = & A_i 
\end{array}

می دانیم  X_i برابر I_nای که ستون iامش با بردار ستونی x تعویض شده است، می باشد. دترمینان ماتریس  X_i را بدست می آوریم:

 \det(X_i) = (-1)^{i+i}x_i \det(I_{n-1}) = 1.x_i.1 = x_i

سپس دترمینان ماتریس حاصل ضرب را بدست می آوریم:

\det(A_i)= \det (AX_i) = \det(A)\det(X_i) = det(A)x_i

که از اینجا خواهیم داشت:

x_i = \frac{\det(A_i)}{\det(A)}

یافتن ماتریس معکوس[ویرایش]

ابتدا ماتریس A ، n×n را در نظر می گیریم

\mathrm{Adj}(A)A = \mathrm{det}(A)I\,

(Adj(A ماتریس الحاقی ماتریس A است و (det(A قابل محاسبه است و I ماتریس همانی است.اگر دترمینان A در R مخالف صفر باشد ،آنگاه دترمینان ماتریس A برابر است با :

A^{-1} = \frac{1}{\operatorname{det}(A)} \operatorname{Adj}(A)

اگر R یک میدان باشد (مثل میدان اعداد حقیقی) در صورتی که det(A)≠0 فرمولی برای محاسبه ماتریس معکوس بدست می آید.به شرطی که (det(A یکتا باشداین فرمول برای هر زمانی که R یک حلقه جابه جایی باشد برقرار است.اگر (det(A یکتا نباشد آنگاه A ماتریس معکوس ندارد.

کاربرد ها[ویرایش]

فرمول صریح برای دستگاه های کوچک[ویرایش]

دستگاه خطی \left\{\begin{matrix}ax+by&={\color{red}e}\\ cx + dy&= {\color{red}f}\end{matrix}\right.\ را در نظر می گیریم که قالب ماترسی آن به صورت \begin{bmatrix} a & b \\ c & d \end{bmatrix}\begin{bmatrix} x \\ y \end{bmatrix}=\begin{bmatrix} {\color{red}e} \\ {\color{red}f} \end{bmatrix}. است.فرض می کنیم ad-bc≠0 باشد.سپس xو y را با قاعده کرامر میابیم: x = \begin{vmatrix} \color{red}{e} & b \\ \color{red}{f} & d \end{vmatrix}/\begin{vmatrix} a & b \\ c & d \end{vmatrix}  = { {\color{red}e}d - b{\color{red}f} \over ad - bc}

و
y = \begin{vmatrix} a & \color{red}{e} \\ c & \color{red}{f} \end{vmatrix}/\begin{vmatrix} a & b \\ c & d \end{vmatrix}  = { a{\color{red}f} - {\color{red}e}c \over ad - bc}

این قانون در ماتریس های 3×3 مشابه است که دستگاه
\left\{\begin{matrix}ax + by + cz&= {\color{red}j}\\dx + ey + fz&= {\color{red}k}\\gx + hy + iz&= {\color{red}l}\end{matrix}\right. فرم ماتریسی ای به صورت
\begin{bmatrix} a & b & c \\ d & e & f \\ g & h & i \end{bmatrix}\begin{bmatrix} x \\ y \\ z \end{bmatrix}=\begin{bmatrix} {\color{red}j} \\ {\color{red}k} \\ {\color{red}l} \end{bmatrix} دارد.

همچنین مقادیرxو y و z از روابط زیر به دست می آیند:

x = \frac { \begin{vmatrix} {\color{red}j} & b & c \\ {\color{red}k} & e & f \\ {\color{red}l} & h & i \end{vmatrix} } { \begin{vmatrix} a & b & c \\ d & e & f \\ g & h & i \end{vmatrix} }, \quad y = \frac { \begin{vmatrix} a & {\color{red}j} & c \\ d & {\color{red}k} & f \\ g & {\color{red}l} & i \end{vmatrix} } { \begin{vmatrix} a & b & c \\ d & e & f \\ g & h & i \end{vmatrix} },\text{ and }z = \frac { \begin{vmatrix} a & b & {\color{red}j} \\ d & e & {\color{red}k} \\ g & h & {\color{red}l} \end{vmatrix} } { \begin{vmatrix} a & b & c \\ d & e & f \\ g & h & i \end{vmatrix} }

هندسه دیفرانسیل[ویرایش]

قاعده کرامر برای حل مسائل هندسه دیفرانسیل بسیار مفید است.دو معادله F(x, y, u, v) = 0\, و G(x, y, u, v) = 0\, را در نظر می گیریم.زمانی که u و v دو متغیر مستقل باشند ، x را x = X(u, v)\, و y را y = Y(u, v)\, تعریف می کنیم. پیدا کردن یک معادله برای \dfrac{\partial x}{\partial u} یک برنامه بدیهی قاعده کرامر است. ابتدا مشتقات F و G و x و y را محاسبه می کنیم.

dF = \frac{\partial F}{\partial x} dx + \frac{\partial F}{\partial y} dy +\frac{\partial F}{\partial u} du +\frac{\partial F}{\partial v} dv = 0
dG = \frac{\partial G}{\partial x} dx + \frac{\partial G}{\partial y} dy +\frac{\partial G}{\partial u} du +\frac{\partial G}{\partial v} dv = 0
dx = \frac{\partial X}{\partial u} du + \frac{\partial X}{\partial v} dv
dy = \frac{\partial Y}{\partial u} du + \frac{\partial Y}{\partial v} dv

dx و dy را در df وdg جایگزین می کنیم و به روابط زیر می رسیم:

dF = \left(\frac{\partial F}{\partial x} \frac{\partial x}{\partial u} +\frac{\partial F}{\partial y} \frac{\partial y}{\partial u} +\frac{\partial F}{\partial u} \right) du + \left(\frac{\partial F}{\partial x} \frac{\partial x}{\partial v} +\frac{\partial F}{\partial y} \frac{\partial y}{\partial v} +\frac{\partial F}{\partial v} \right) dv = 0
dG = \left(\frac{\partial G}{\partial x} \frac{\partial x}{\partial u} +\frac{\partial G}{\partial y} \frac{\partial y}{\partial u} +\frac{\partial G}{\partial u} \right) du + \left(\frac{\partial G}{\partial x} \frac{\partial x}{\partial v} +\frac{\partial G}{\partial y} \frac{\partial y}{\partial v} +\frac{\partial G}{\partial v} \right) dv = 0

تا زمانی که u و v دو متغیر مستقل باشند ، ضرایب du و dv حتماً باید صفر باشد.سپس ما می توانیم معادلات ضرایب را بنویسیم:

\frac{\partial F}{\partial x} \frac{\partial x}{\partial u} +\frac{\partial F}{\partial y} \frac{\partial y}{\partial u} = -\frac{\partial F}{\partial u}
\frac{\partial G}{\partial x} \frac{\partial x}{\partial u} +\frac{\partial G}{\partial y} \frac{\partial y}{\partial u} = -\frac{\partial G}{\partial u}
\frac{\partial F}{\partial x} \frac{\partial x}{\partial v} +\frac{\partial F}{\partial y} \frac{\partial y}{\partial v} = -\frac{\partial F}{\partial v}
\frac{\partial G}{\partial x} \frac{\partial x}{\partial v} +\frac{\partial G}{\partial y} \frac{\partial y}{\partial v} = -\frac{\partial G}{\partial v}

حالا با توجه به قاعده کرامر می بینیم که :


\frac{\partial x}{\partial u} = \frac{\begin{vmatrix} -\frac{\partial F}{\partial u} & \frac{\partial F}{\partial y} \\ -\frac{\partial G}{\partial u} & \frac{\partial G}{\partial y}\end{vmatrix}}{\begin{vmatrix}\frac{\partial F}{\partial x} & \frac{\partial F}{\partial y} \\ \frac{\partial G}{\partial x} & \frac{\partial G}{\partial y}\end{vmatrix}}

که این فرمول دو جمله از ماتریس ژاکوبی است.

\frac{\partial x}{\partial u} = - \frac{\left(\frac{\partial\left(F, G\right)}{\partial\left(u, y\right)}\right)}{\left(\frac{\partial\left(F, G\right)}{\partial\left(x, y\right)}\right)}

همچنین این روابط را می توان برای \frac{\partial x}{\partial v}, \frac{\partial y}{\partial u}, \frac{\partial y}{\partial v} به دست آورد.

برنامه ریزی عدد صحیح[ویرایش]

معادلات دیفرانسیل معمولی[ویرایش]

قاعده کرامر برای به دست آوردن جواب عمومی معادله دیفرانسیل خطی ناهمگن با استفاده از روش تغییر پارامترها استفاده می شود.

تعبیر هندسی[ویرایش]

تعبیر هندسی قاعده کرامر. مساحت های متواضی الاضلاع های هاشور خورده‌ی دوم و سوم یکسان هستند و متوازی‌الأضلاع دوم  x_1 برابر اولی است. قاعده کرامر از این برابری ها استفاده می کند.

قاعده کرامر تعبیر هندسی دارد که می توان از آن برای اثبات یا ساده کردن تصور ماهیت هندسی قاعده کرامر استفاده کرد.

دستگاه معادلات داده شده زیر را در نظر بگیرید:

\begin{matrix}a_{11}x_1+a_{12}x_2&=b_1\\a_{21}x_1+a_{22}x_2&=b_2\end{matrix}

می توان دستگاه را بصورت معادله ای بین دو بردار در نظر گرفت.

x_1\binom{a_{11}}{a_{21}}+x_2\binom{a_{12}}{a_{22}}=\binom{b_1}{b_2}.

مساحت متوازی‌الأضلاع هایی که از روابط \binom{a_{11}}{a_{21}} و \binom{a_{12}}{a_{22}} بدست می آیند، را می توان از دترمینان دستگاه معادلات بدست آورد:

\left|\begin{matrix}a_{11}&a_{12}\\a_{21}&a_{22}\end{matrix}\right|.

بصورت کلی اگر تعداد متغیر ها از معادلات بیشتر باشد، دترمینان n بردار از طول n حجم ''متوازی السطوح'' که از آن بردار ها در فضای اقلیدسی n بعدی ساخته می شود، را محاسبه می کند.

بنابراین مساحت متوازی‌الأضلاع ای که از x_1\binom{a_{11}}{a_{21}} و \binom{a_{12}}{a_{22}} بدست می آید، باید x_1 برابر مساحت اولی باشد زیرا یکی از اضلاع آن توسط این تابع چند برابر شده است. حال مسحات آخرین متوازی‌الأضلاع، با استفاده از اصل کاوالیری، مساحتی برابر با متوازی‌الأضلاعی است که از \binom{b_1}{b_2}=x_1\binom{a_{11}}{a_{21}}+x_2\binom{a_{12}}{a_{22}} و \binom{a_{12}}{a_{22}} بدست می آید.

برابر کردن مساحت های آخرین و دومین متوازی‌الأضلاع معادله \left|\begin{matrix}b_1&a_{12}\\b_2&a_{22}\end{matrix}\right|=\left|\begin{matrix}a_{11}x_1&a_{12}\\a_{21}x_1&a_{22}\end{matrix}\right|=x_1\left|\begin{matrix}a_{11}&a_{12}\\a_{21}&a_{22}\end{matrix}\right| را می دهد که قاعده کرامر از آن استفاده می کند.

اثبات کوتاه[ویرایش]

اثباتی کوتاه برای قاعده کرامر می توان ارئه داد. فرض می کنیم x_1 دترمینان ماتریس زیر باشد.

X_1=\begin{bmatrix}
x_1 & 0 & 0 & \dots & 0\\
x_2 & 1 & 0 & \dots & 0\\
x_3 & 0 & 1 & \dots & 0\\
\vdots & \vdots & \vdots & \ddots &\vdots \\
x_n & 0 & 0 & \dots & 1
\end{bmatrix}

از سوی دیگر، قرض کنید ماتریس اصلی ما A معکوس پذیر باشد، ماتریس X_1 ستون های A^{-1}  b , A^{-1}  v_2 , \ldots, A^{-1}  v_n را دارد که v_k k-امین بردار ماتریس A باشد. باید آورید که A_1 ستون های   b ,  v_2, \ldots,   v_n را دارا می باشد. بنابراین ما  x_1= \det (X_1) = \det (A^{-1}) \det (A_1)= \frac{\det (A_1)}{\det (A)} را خواهیم داشت که همان چیزی است که دنبالش می گشتیم. اثبات بقیه x_j بطور مشابه می باشد.

موارد ناسازگار و نامعین[ویرایش]

یک دستگاه معادله زمانی ناسازگار است که هیچ جوابی ندارد و زمانی نا مشخص است که بیش از یک جواب داشته باشد.برای معادلات خطی دستگاه نامعین بی شمار جواب خواهد داشت (اگر میدان نامحدود باشد).ار آنجاییکه جواب می تواند در جمله ای از یک یا چند پارامتر بیان شود پس می تواند مقادیر دلخواه بگیرد. قاعده کرامر جایی که دترمینان مخالف صفر باشد روی مورد اعمال می شود.در مورد مقابل دستگاه بر اساس مقدار دترمینان برای دستگاه های 2×2 یا نامعین است یا ناسازگاز. برای دستگاه های 3×3 یا بالاتر باید به نکته ای اشاره کرد که اگر ماتریس ضاریب دترمینان مساوی با صفر باشد اگر صورت کسر دترمینان مخالف صفر بود حتماً این دستگاه ناسازگار است. اگرچه این حرف اشتباه است که :دترمینان های مساوی صفر به اینکه دستگاه نامعین است اشاره ندارند.در مثال زیر دترمینان ها مساوی صفر هستند ولی دستگاه 3×3 هنوز نامعین است.  x + y + z = 1, x + y + z = 2, x + y + z = 3

جستارهای وابسته[ویرایش]

یادداشت ها[ویرایش]

  1. Cramer, Gabriel (1750). "Introduction à l'Analyse des lignes Courbes algébriques" (in French). Geneva: Europeana. pp. 656–659. Retrieved 2012-05-18. 
  2. MacLaurin, Colin (1748). A Treatise of Algebra, in Three Parts.. 
  3. Boyer, Carl B. (1968). A History of Mathematics (2nd ed.). Wiley. p. 431. 
  4. Katz, Victor (2004). A History of Mathematics (Brief ed.). Pearson Education. pp. 378–379. 
  5. Hedman, Bruce A. (1999), "An Earlier Date for "Cramer's Rule"", Historia Mathematica, 4(26): 365–368, doi:10.1006/hmat.1999.2247 
  6. Ken Habgood, Itamar Arel (2012). "A condensation-based application of Cramerʼs rule for solving large-scale linear systems". Journal of Discrete Algorithms 10: 98–109. doi:10.1016/j.jda.2011.06.007. 

پیوند به بیرون[ویرایش]

جستجو در ویکی‌نَسک در ویکی‌کتاب کتابی با عنوان: Linear Algebra/Cramer's Rule وجود دارد.