ریاضیات

روش Runge-Kutta

از لحاظ تاریخی، معادلات دیفرانسیل در شیمی، فیزیک و مهندسی به وجود آمده است. اخیرا، آنها نیز در پزشکی، زیست شناسی، انسان شناسی، و مانند آن بوجود آمده است. با این وجود ما قصد داریم خودمان را به معادلات دیفرانسیل عادی (ODE) محدود کنیم، با تاکید ویژه بر مسائل مربوط به مقادیر اولیه (IVP)، که به اصطلاح به این دلیل است که شرایط در حل معادلات دیفرانسیل، در ابتدای مسیر مشخص شده است یعنی آنها شرایط اولیه هستند [1].

در [2] مشخص شده است که در میان مدل های استفاده از معادلات دیفرانسیل، معادلات دیفرانسیل معمولی (ODE) اغلب برای توصیف مشکلات مختلف فیزیکی، به عنوان مثال، حرکت سیارات در میدان گرانشی مانند مشکل کپلر، آونگ ساده ، مدارهای الکتریکی و مشکلات سینتیکی شیمیایی. ODE دارای فرم است:

y ¢ (x) = f (x، y (x))

(1)

جایی که x متغیر مستقل است که اغلب به زمان در یک مشکل فیزیکی اشاره دارد و متغیر وابسته y (x)، راه حل است. از آنجا که y (x) می تواند یک تابع ارزش بردار بعدی N باشد، دامنه و محدوده معادله دیفرانسیل معمول، f و راه حل y توسط:

(2)

ODE بالا نامیده می شود غیر خودمختار است، زیرا f یک تابع از x و y است. با این حال، به سادگی با معرفی یک متغیر اضافی، که همیشه دقیقا با x برابر است، می تواند به راحتی در یک فرم معادل «مستقل» بازنویسی شود:

y ¢ (x) = f (y (x))

جایی که f تنها تابع y است.

متأسفانه، بسیاری از مشکلات مربوط به ODE دقیقا نمیتوان حل کرد. به همین دلیل توانایی عددی تقریب این روش ها بسیار مهم است [2].

راه حل عددی از ODE ها مهم ترین تکنیک است که تا به حال در پویایی زمان مداوم توسعه یافته است. از آنجا که اکثر ODE ها از نظر تحلیلی قابل حل نیستند، ادغام عددی تنها راه کسب اطلاعات در مورد مسیر است. بسیاری از روش های مختلف پیشنهاد شده و مورد استفاده در تلاش برای حل دقیق، انواع مختلف ODE است. با این حال، تعداد زیادی از روش های شناخته شده و استفاده شده در جهان (یعنی Runge-Kutta، Adam-Bashforth-Moulton و فرمول تفاوت عقب مانده) وجود دارد. همه اینها سیستم دیفرانسیل را برای ایجاد یک معادله یا نقشه اختلاف [3] را کاهش می دهند.

این روش ها، نقشه های مختلفی را از همان معادله به دست می آورند، اما آنها هدف مشابهی دارند. که دینامیک نقشه ها باید به طور دقیق مطابق با پویایی معادلات دیفرانسیل باشد. از خانواده الگوریتم Runge-Kutta، روش های شناخته شده و مورد استفاده برای ادغام عددی [4] آمده است.

با ظهور رایانه ها، روش های عددی در حال حاضر به طور فزاینده ای جذاب و کارآمد برای به دست آوردن راه حل های تقریبی برای معادلات دیفرانسیل است که تا کنون ثابت شده است و حتی تحلیلی غیرممکن است. با این حال، برای این کار، ما به ویژه در کلاس روش های اولیه پیشنهاد شده توسط دیوید رنج (1856-1927) [5]، یک ریاضیدان و فیزیکدان آلمانی، علاقه مند شدیم و توسط یکی دیگر از ریاضیدان آلمانی به نام ویلهلم Kutta (1944-1867) [6] به سیستم معادلات؛ یک روش معمول به روش Runge-Kutta اشاره دارد.

مواد و روش

دینامیک روش Runge-Kutta

ما IVP را در نظر می گیریم:

y ¢ = f (x، y)، y (a) = α

(3)

روش Runge-Kutta برای حل معادله (3)، روشهای یک مرحله ای هستند که برای تقریب متدهای سری تیلور طراحی شده اند، اما مزیت این است که نیازی به ارزیابی صریح مشتقات f (x، y) ندارند ، که x اغلب زمان را نشان می دهد (t). ایده اصلی این است که از ترکیب خطی از مقادیر f (x، y) برای تقریبی y (x) استفاده کنیم. این ترکیب خطی تا حد ممکن نزدیک تر می شود، با مجموعه ی تیلور برای y (x) برای به دست آوردن روش های بالاترین احتمال ممکن است. فرض می شود که مقدار اولیه (x _0، y ₀ ) با توجه به معادله انحصاری نیست و یک راه حل وجود دارد که می تواند در مجموعه تیلور توسعه یابد . [7]

بر طبق [8]، [9]، روش Runge-Kutta S-stage، به صورت زیر تعریف می شود:

	(4)
	(5)
	(6)

با استفاده از

k = [k ₁ ، k ₂ ، ...، k _s ]

دامنه ها،

b = [b ₁ ، b ₂ ، ...، b _s ]

وزن ها و

c = [c ₁ ، c ₂ ، ...، c _s ]

ابسوسا

روش SK مرحله RK نیاز به ارزیابی عملکرد توابع در هر مرحله دارد. هر یک از توابع k _r = (x، y، h)، r = 1، 2 ... s ممکن است به عنوان تقریبی به مشتق y ¢ (x) تفسیر شود و تابع f (x، y، h) به عنوان وزن میانگین این تقریبها. ثبات، مستلزم آن است که Σ ^s_{r = 1} b _r= 1 باشد.

تشخیص یک روش Runge-Kutta S-Stage

با توجه به [1]، سه روش برای استخراج روش Runge-Kutta وجود دارد:

· گسترش سری تیلور؛
· مفهوم جبری درختان ریشه ای
· جبر کامپیوتر

در این مقاله، بحث ما بر روی روش گسترش سری تیلور خواهد بود.

فرایند تولید یک روش داده شده توسط RK توسط گسترش سری تیلور می تواند به سه مرحله زیر خلاصه شود:

· مرحله 1 :

به دست آوردن مجموعه سری تیلور k _r (دامنه ها) تعریف شده توسط:

k _r = f (z _r ، y _n + hΣ _s a _rj k _j )

(7)

جایی که: z _r = x _n + c _r h، r = 1 (1) s در مورد نقطه (x _n ، y _n ) در فضای راه حل.

· مرحله 2:

قرار دادن این گسترش ها و c _r (c _r = Σ ^s_{j = 1} a _rj ، r = 1 (1) به بیان روش RK عمومی S-مرحله، به صورت زیر است:

f _RK = Σ _s b _j k _j ، s≥1

(8)

· مرحله 3:

مقایسه ضرایب در قدرت ساعت برای هر دو تابع افزایش F _RK از روش رانگ کوتا مرتبه چهار-داده شده در معادله (8) بالا و عملکرد افزایش F _T برای تیلور روش بسط توسط مشخص شده

[8]، [9] و [10] نشان داده شده است که اگر این توابع با شرایط در h ^p موافق باشند ، این فرایند به ترتیب p است. مجموع ضرایب ناشناخته { _bj ، c _r ، a _rj ، j = 1 (1s)} به طور معمول بیش از تعداد معادلات است و پارامترهای آزاد را به ما می دهد که می توانیم مقادیر آن را تعیین کنیم [11].

ریچاردسون استخراج

یک نقص عمده در روش Runge-Kutta این است که برای مشاهده خطاها دشوار و پیچیده است. با توجه به [8]، " محدوده خطاهای مختلط محلی، پایه مناسب برای نظارت بر خطای کوتاه شدن محلی را ایجاد نمی کند، با توجه به ساخت یک سیاست کنترل مرحله ای مشابه آنچه که برای روش پیش بینی کننده اصلاح شده طراحی شده است. آنچه که مورد نیاز است، در عوض یک محدوده، تخمین قابل قبول محاسبه خطای تخریب محلی است، شبیه به آنچه که توسط دستگاه Milne برای جفت های پیش بینی کننده-اصلاح کننده به دست آمده است . "

برآوردی که ما ارائه می دهیم ناشی از کاربرد فرآیند رویکرد تعلیق به حد است، که در غیاب به عنوان Extrapolation ریچاردسون شناخته می شود. این شامل حل مسئله دو بار با استفاده از اندازه گام ها h و 2h است.

در زیر فرض محلی سازی که هیچ خطای قبلی ایجاد نشده است، می توانیم نوشت:

y (x _{n + 1} ) - y _{n + 1} = T _{n + 1} = φ (x _n ، y (x _n )) h ^{p + 1} + o (h ^{p + 2} )

(10)

جایی که p به ترتیب روش Runge-Kutta است، φ (x _n ، y (x _n )) h ^{p + 1} خطای اصلی تکه تکه شدن محلی است.

بعد، ما y ^*_{n + 1} ، تقریبی دوم به y (x _{n + 1} ) محاسبه می کنیم ، که با استفاده از همان روش در x _n-1 با steplenght 2h بدست می آید. بر اساس یک فرض محلی سازی، از این می شود که:

y (x _{n + 1} ) - y ^*_{n + 1} = φ (x _n-1 ، y (x _n-1 )) (2h) ^{p + 1} + o (h ^{p + 2} )

(11)

و در گسترش φ (x _n-1 ، y (x _n-1 )) در مورد (x _n ، y _n ):

y (x _{n + 1} ) - y ^*_{n + 1} = φ (x _n ، y (x _n )) (2h) ^{p + 1} + o (h ^{p + 2} )

(12)

در تفریق (10) از (12)، ما دریافت می کنیم:

y (x _{n + 1} ) - y ^*n_{+ 1} = (2 ^{p + 1} - 1) φ (x _n ، y (x _n )) h ^{p + 1} + o (h ^{p + 2} )

بنابراين، خطاي اصلي ترك كردن موضعي كه به عنوان برآورد خطاي كوتاه مدت در نظر گرفته مي شود، مي تواند به صورت زير باشد:

φ (x _n ، y (x _n )) h ^{p + 1}= Tn + 1 = (y (x _{n + 1} ) - y ^*_{n + 1} ) / (2 ^{p + 1} - 1)

(13)

T _{n + 1} = (y (x _{n + 1} ) -y ^*_{n + 1} ) / (2 ^{p + 1} -1)

(14)

معادله (14) به معنای به دست آوردن تخمین های سریع خطاهای مختلط محلی در محاسبات با استفاده از هر Runge-Kutta S است، بدون اینکه اولین راه حل دقیق را بدست آوریم.

آزمایشات عددی

ما به وسیله حل معادله (14) با حل مسئله ارزش اولیه خودمختار، اثربخشی روش Extrapolation ریچاردسون را نشان خواهیم داد.

y '= x + y؛ y (0) = 1 (جواب دقیق: y _E = 2e ^x -x-1 )

در steplenghts h = 0.1 و h = 0.2 است.

روش ما برای تحقیق ما از روش Runge-Kutta شش مرحله بسیار کارا با پنج قاشق غذاخوری استفاده می کند:

از این پس ما به این روش به عنوان RK65 اشاره خواهیم کرد.

نتایج و بحث ها

نتایج زیر ارائه شده است:

جدول .1 نتایج آزمایش تجربی

ساعت	ایکس	RK65	دقیق	خطا واقعی
	0.0	1.0	1.0	0.0
0.1	0.1	1.110341796	1.110341836	4.01513E-08
	0.2	1.242805427	1.242805516	8.93203E-08
	0.3	1.399717467	1.399717615	1.48152E-07
	0.4	1.583649177	1.583649395	2.18283E-07
	0.5	1.79744224	1.797442541	3.014E-07
	0.6	2.044237201	2.044237601	3.99781E-07
	0.7	2.327504899	2.327505415	5.15941E-07
	0.8	2.651081205	2.651081857	6.51985E-07
	0.9	3.019205412	3.019206222	8.10314E-07
	1.0	3.436562662	3.436563657	9.94918E-07
	0.0	1.000000000	1.000000000	0،00000000000
0.2	0.2	1.242803057	1.242805516	2.45932E-06
	0.4	1.583643388	1.583649395	6.00728E-06
	0.6	2.044226595	2.044237601	1.10058E-05
	0.8	2.651063934	2.651081857	1.7923E-05
	1.0	3.436536293	3.436563657	2.73639E-05

معمولا برای بدست آوردن خطاها، راه حل دقیق و تقریب های عددی به دست می آید و تفاوت آنها در هر مرحله خطا در هر مرحله می دهد. هدف ما در این مقاله نشان دادن این است که در واقع ممکن است چنین اشتباهی را بدون نیاز به راه حل دقیق برای اولین بار بدست آوریم.

بعد، معادله (14) برای برآورد خطا استفاده می شود که به راه حل های دقیق بستگی ندارد.

به یاد آوردن معادله (14):

T _{n + 1} = (y (x _{n + 1} ) -y ^*_{n + 1} ) / (2 ^{p + 1} -1)

جایی که: y _{n + 1} محلول تقریبی با h = 0.1 است؛ y ^*_{n + 1} راه حل تقریبی با h = 0.2 است؛ p روش روش است یعنی p = 5.

از این رو معادله (14) می شود:

T _{n + 1} = (y (x _{n + 1} ) -y ^*_{n + 1} ) / 63

باید اشاره کرد که آنچه معادله (14) ارائه می دهد، برآورده می شود، اما این برآوردها به ما می گوید که طبیعت و نظم اشتباهاتی که ما با آن مواجه هستیم و زمانی که راه حل های تحلیلی قابل دستیابی نیست، این روش تنها گزینه ای است که در دسترس است .

در x = 0.2: T _{n + 1} = 1.242805427 - 1.242803057 / 63 = 3.7619E-08

در x = 0.4: T _{n + 1} = 1.583649177 - 1.583643388 / 63 = 9.189E - 08

در x = 0.6: T _{n + 1} = 2.044237201 - 2.044226595 / 63 = 1.684E - 07

در x = 0.8: T _{n + 1} = 2.651081205 - 2.651063934 / 63 = 2.74E - 07

در x = 1.0: T _{n + 1} = 3.43656362 - 3.436536293 / 63 = 4.186E - 07

مقایسه مقادیر خطا و خطای واقعی در جدول 2 نشان داده شده است.

جدول 2 خلاصه ای از نتایج برای اشتباهات واقعی و خطاهای تخمینی

ایکس	خطا واقعی	برآورد خطا
0.2	8.90E-08	3.76E-08
0.4	2.18E-07	9.19E-08
0.6	4.00E-07	1.68E-07
0.8	6.52E-07	2.74E-07
1.0	9.95E-07	4.19E-07

شکل 1 نمودار مقایسه خطاهای واقعی و خطاهای تخمینی

از شکل 1 ما می توانیم از منحنی های راه حل ببینیم که منحنی برآورد خطا با استفاده از استخراج ریچاردسون بسیار نزدیک به منحنی راه حل عددی برای RK65 برای h = 0.1 است.

شاخص های برآوردهای ما به طور مطلوب با خطاهای واقعی h = 0.1 (بین 10 ^-7 -10 ^-8 ) مقایسه می شود. با این حال، برای h = 0.2، تخمین خطا ما و همچنین راه حل برای h = 0.1، هم بسیار دور از خطاهای واقعی است که خوب است به عنوان دقت است که با افزایش در steplenght کاهش می یابد. بنابراین نتیجه ما با واقعیت سازگار است.

نتیجه گیری

بنابراین می توان نتیجه گرفت که هنگام استفاده از روش های Runge-Kutta برای حل مشکلات غیر سفت، ما نیازی به محاسبه راه حل دقیق نیستیم تا بتوانیم خطاهای را محاسبه کنیم. Extrapolation ریچاردسون یک برآوردگر خطای قابل قبول را فراهم می کند که قادر به ارائه یک ایده کارآمد از ماهیت و درجه اشتباهات است.

همانطور که بیشتر معادلات دیفرانسیلی تحلیلی محلول نیست، راه حل دقیق نمی تواند به دست آید و از این رو امکان اشتباه برای چنین مشکلی ایجاد نمی شود. با این حال، استخراج ریچاردسون یک وسیله عالی برای حل این مشکل است، زیرا برای رسیدن به برآوردهای خطا لازم نیست که راه حل دقیق مورد نیاز باشد.

+ نوشته شده در سه شنبه سیزدهم آذر ۱۳۹۷ ساعت 10:50 توسط علی رضا نقش نیلچی |

y ¢ (x) = f (x، y (x))

y ¢ = f (x، y)، y (a) = α

k = [k ₁ ، k ₂ ، ...، k _s ] دامنه ها، b = [b ₁ ، b ₂ ، ...، b _s ] وزن ها و c = [c ₁ ، c ₂ ، ...، c _s ]

ن وزن میانگین این تقریبها. ثبات، مستلزم آن است که Σ ^s_{r = 1} b _r= 1

خطای قطع در جهان در است

در حالی که خطای تخریب محلی است

+ نوشته شده در سه شنبه سیزدهم آذر ۱۳۹۷ ساعت 10:33 توسط علی رضا نقش نیلچی |

+ نوشته شده در سه شنبه سیزدهم آذر ۱۳۹۷ ساعت 9:46 توسط علی رضا نقش نیلچی |

+ نوشته شده در سه شنبه سیزدهم آذر ۱۳۹۷ ساعت 9:38 توسط علی رضا نقش نیلچی |

+ نوشته شده در سه شنبه سیزدهم آذر ۱۳۹۷ ساعت 9:30 توسط علی رضا نقش نیلچی |

+ نوشته شده در سه شنبه سیزدهم آذر ۱۳۹۷ ساعت 9:30 توسط علی رضا نقش نیلچی |

روش Runge-Kutta

+ نوشته شده در سه شنبه سیزدهم آذر ۱۳۹۷ ساعت 9:28 توسط علی رضا نقش نیلچی |

+ نوشته شده در سه شنبه سیزدهم آذر ۱۳۹۷ ساعت 9:27 توسط علی رضا نقش نیلچی |

+ نوشته شده در سه شنبه سیزدهم آذر ۱۳۹۷ ساعت 9:26 توسط علی رضا نقش نیلچی |

روش های روشنی Runge-Kutta

$y_ {n 1} = y_ {n} h \ sum_ {i = 1} ^ {s} b_ {i} k_ {i}$

که در آن

${\ displaystyle {\ begin {aligned} k_ {1} & = f (t_ {n}Ø y_ {n})Ø \\ k_ {2} & = f (t_ {n} + c_ {2} hØ y_ {n} + h (a_ {21} k_ {1}))Ø \\ k_ {3} & = f (t_ {n} + c_ {3} hØ y_ {n} + h (a_ {31} k_ {1} + a_ {32} k_ {2}))Ø \\ Ù \\ \ vdots \\ k_ {s} & = f (t_ {n} + c_ {s} hØ y_ {n} + h ( a_ {s1} k_ {1} + a_ {s2} k_ {2} + \ cdots + a_ {sØ s-1} k_ {s-1})). \ end {aligned}}}$

+ نوشته شده در سه شنبه سیزدهم آذر ۱۳۹۷ ساعت 7:27 توسط علی رضا نقش نیلچی |

خطا روش عددی

+ نوشته شده در سه شنبه سیزدهم آذر ۱۳۹۷ ساعت 2:13 توسط علی رضا نقش نیلچی |

روش hولر ساده است، اما اگر گام بیش از حد انتخاب شود خطای القا شده می تواند بسیار بالا باشد. در واقع، محاسبه خطای سازگاری با فرمول تیلور-لاگرانژ ارائه می شود :

+ نوشته شده در سه شنبه سیزدهم آذر ۱۳۹۷ ساعت 2:1 توسط علی رضا نقش نیلچی |

اولری جلوبر

+ نوشته شده در سه شنبه سیزدهم آذر ۱۳۹۷ ساعت 1:43 توسط علی رضا نقش نیلچی |

روش هون

+ نوشته شده در سه شنبه سیزدهم آذر ۱۳۹۷ ساعت 1:27 توسط علی رضا نقش نیلچی |

روش متمایز صریح

+ نوشته شده در سه شنبه سیزدهم آذر ۱۳۹۷ ساعت 1:25 توسط علی رضا نقش نیلچی |

Euler اویلر

روش اویلر مرتبه اول است. فقدان ثبات و دقت، محبوبیت آن را عمدتا به عنوان یک مثال مقدماتی ساده از روش راه حل عددی استفاده می کند.

$\ begin {array} {c | c} 0 Ù 0 \\ \ hline Ù 1 \\ \ end {array}$

+ نوشته شده در سه شنبه سیزدهم آذر ۱۳۹۷ ساعت 1:24 توسط علی رضا نقش نیلچی |

رانگ−کوتای

+ نوشته شده در سه شنبه سیزدهم آذر ۱۳۹۷ ساعت 1:14 توسط علی رضا نقش نیلچی |

+ نوشته شده در سه شنبه سیزدهم آذر ۱۳۹۷ ساعت 1:8 توسط علی رضا نقش نیلچی |

روش های آدامز-بولتون

+ نوشته شده در سه شنبه سیزدهم آذر ۱۳۹۷ ساعت 0:44 توسط علی رضا نقش نیلچی |

قضیه باقی مانده چینی 3

قضیه باقی مانده چینی (CRT - Theorem of Chinese Reminder) برای حل انواع معادلات با یک متغیر استفاده می شود، اما با ماژول های متقابل ساده متفاوت است، همانطور که در زیر نشان داده شده است:

$\ tt \ parindent0pt x \ equiv a_ {1} (mod \ m_ {1}) x \ equiv a_ {2} (mod \ m_ {2}) ... x \ equiv a_ {k} (mod \ m_ {k}$

قضیه چینی باقی مانده بیان می کند که معادلات فوق یک راه حل منحصر به فرد دارند اگر ماژول ها به طور متقابل ساده باشند.

$\ tt \ parindent0pt $ x \ equiv 2 (mod \ 3) $ x \ equiv 3 (mod \ 5) $ x \ equiv 2 (mod \ 7) $$

$23 \ equiv 3 \ left ({\ bmod 5} \ right)$

$23 \ equiv 2 \ left ({\ bmod 3} \ right)$

$23 \ equiv 2 \ left ({\ bmod 7} \ right)$

پس برای این سیستم معادلات، x = 23 است .

راه حل سیستم معادلات به ترتیب زیر انجام می شود:

یافتن $M = {m_1} \ times {m_2} \ times \ ldots \ times {m_k}$ . این یک ماژول رایج است.
یافتن M ₁ = M / m ₁ ، M ₂ = M / m ₂ ، ...، M _k = M / m _k .
با استفاده از ماژول های مربوطه m ₁ ، m ₂ ، ....، M _k ، چندتایی را پیدا کنیمعکوس M ₁ ، M ₂ ، را به عنوان M ₁^-1 ، M ₂^-1 ، ...، M _k^{-1 تعیین کنیم} .

توجه داشته باشید که سیستم معادلات ممکن است یک راه حل داشته باشد، حتی اگر ماژول ها به طور متقارن ساده نیستند. با این حال، در رمزنگاری، ما فقط علاقه مند به حل معادلات با ماژول های متقارن ساده هستیم.

یک راه حل برای سیستم معادلات پیدا کنید

$\ tt \ parindent0pt $ x \ equiv 2 (mod \ 3) $ x \ equiv 3 (mod \ 5) $ x \ equiv 2 (mod \ 7) $$

قضیه باقی مانده چینی اغلب در رمزنگاری استفاده می شود. یکی از چنین کاربردی - حل معادلات درجه دوم - در بخش بعدی مورد بحث قرار خواهد گرفت.یک برنامه دیگر نمایندگی از عدد بسیار بزرگ به عنوان یک لیست از عدد صحیح کوچک است.

فرض کنید ما باید z = x + y را محاسبه کنیم ، جایی که x = 123 و y = 334 ، اما سیستم فقط اعداد کمتر از 100 را قبول می کند . این اعداد را می توان با معادلات زیر بیان کرد:

قرار دادن هر معادله X با معادله مربوطه Y :

اکنون این سه معادله را می توان با استفاده از قضیه چینی بر روی باقی مانده برای یافتن z حل کرد . یکی از پاسخهای قابل قبول z = 457 است .

ادامه نوشته

+ نوشته شده در شنبه سوم آذر ۱۳۹۷ ساعت 0:44 توسط علی رضا نقش نیلچی |

مثال از قضیه چینی2

فرمول اصلی Sunzi: x ≡ 2 (mod 3) ≡ 3 (mod 5) ≡ 2 (mod 7) با راه حل x = 23 + 105 k که در آن k ∈ ℤ

+ نوشته شده در جمعه دوم آذر ۱۳۹۷ ساعت 20:22 توسط علی رضا نقش نیلچی |

تغییرات و تعمیم ها قضیه چینی

$i,j\in \{1,\dots ,n\},i\neq j$

$\ker \varphi _{i}+\ker \varphi _{j}=A$

$\Phi \colon A\to \prod _{{i=1}}^{n}B_{i}$

که همریخت طبیعی هستند

+ نوشته شده در جمعه دوم آذر ۱۳۹۷ ساعت 18:57 توسط علی رضا نقش نیلچی |

الگوریتم گارنر برای قضیه چینی

مجموعه ای از ماژول ها را در نظر بگیرید

(a_ {1}، a_ {2}، \ dots، a_ {n})

رضایت شرایط قضیه برآورده کند. قضیه دیگری از نظریه اعداد بیانگر هر عدد است

$0 \ leqslant x <M = a_ {1} \ cdot a_ {2} \ cdot \ ldots \ cdot a_ {n}$ به طور یکنواخت قابل نمایش است به عنوان

$x = x_ {1} + x_ {2} \ cdot a_ {1} + x_ {3} \ cdot a_ {1} \ cdot a_ {2} + \ dots + x_ {n} \ cdot a_ {1} \ cdot a_ {2} \ cdot \ ldots \ cdot a _ {{n-1}}$

$x_ {1} = r_ {1}$

$r_ {2} = (x_ {1} + x_ {2} a_ {1}) {\ bmod {a_ {2}}}$

$x_ {2} = (r_ {2} -x_ {1}) r _ {{12}} {\ bmod {a_ {2}}}$

$r_ {3} = (x_ {1} + x_ {2} a_ {1} + x_ {3} a_ {1} a_ {2}) {\ bmod {a_ {3}}}$

$x_ {3} = ((r_ {3} -x_ {1}) r _ {{13}} - x_ {2}) r _ {{23}} {\ bmod {a_ {3}}$

الگوریتم گارنر برای قضیه چینی

برای  ( int  i  =  0 ؛  i  <  n ؛  i ++ )  { 
	x [ i ]  =  باقی مانده [ i ]؛ 
	برای  ( int  j  =  0 ؛  j  <  i ؛  j ++ )  { 
		x [ i ]  =  inverses [ j ] [ i ]  *  ( x [ i ]  -  x [j ])؛ 
		x [ i ]  =  x [ i ]  ٪  a [ i ]؛ 
		اگر  ( x [ i ]  <  0 ) 
			x [ i ]  + =  a [ i ]؛ 
	} 
}

الگوریتم گارنر برای قضیه چینی

for (int i = 0; i < n; i++) {
	x[i] = remainders[i];
	for (int j = 0; j < i; j++) {
		x[i] = inverses[j][i] * (x[i] - x[j]);
		x[i] = x[i] % a[i];
		if (x[i] < 0)
			x[i] += a[i];
	}
}

ادامه نوشته

+ نوشته شده در جمعه دوم آذر ۱۳۹۷ ساعت 13:22 توسط علی رضا نقش نیلچی |

الگوریتم بر اساس قضیه چینی بر روی باقی مانده :

مرحله 1. محاسبه کنید :

$M = {\ displaystyle \ prod_ {{i = 1}} ^ {n} a_ {i}}$

مرحله 2 برای همه $i \ in \ {1Ø2Ø \ dotsØ n \}$ ما پیدا میکنیم :

$M_ {i} = {\ frac M {a_ {i}}}$

مرحله 3. پیدا کردن :

$M_ {i} ^ {{- 1}} = {\ frac 1 {M_ {i}}} {\ bmod {a_ {i}}}$

مرحله 4. مقدار دلخواه را با فرمول محاسبه کنید

$x = \ sum _ {{i = 1}} ^ {n} r_ {i} M_ {i} M_ {i} ^ {{- 1}} \ mod M$

+ نوشته شده در جمعه دوم آذر ۱۳۹۷ ساعت 13:6 توسط علی رضا نقش نیلچی |

مثال از قضیه چینی

${\ displaystyle {\ begin {cases} x \ equiv 1 {\ pmod {2}}Ø \\ x \ equiv 2 {\ pmod {3}}Ø \\ x \ equiv 6 {\ pmod {7}}. \\ Ù¾Ø§ÛØ§Ù {ÙÙØ§Ø±Ø¯}}}$

برای حل این سیستم، ما راه حل های معادلات اول، دوم و سوم را به صورت جداگانه می نویسیم (به اندازه کافی برای نوشتن راه حل هایی که از 2 × 3 × 7 = 42 استفاده نمی کنند ):

${\ displaystyle x_ {1} \ in \ {1Ø3Ø5Ø7Ø9Ø11Ø \ dotsØ 39Ø \ mathbf {41}Ø 43Ø \ dots}}}$

${\ displaystyle x_ {2} \ in \ {2Ø5Ø8Ø11Ø14Ø \ dotsØ 38Ø \ mathbf {41}Ø 44Ø \ dots \}Ø}$

${\ displaystyle x_ {3} \ in \ {6Ø13Ø20Ø27Ø34Ø \ mathbf {41}Ø 48Ø \ dots}}.$

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

$x \ in \ {41Ø83Ø125Ø \ dots \}$

$x \ equiv 41 {\ pmod {42}}.$

به منظور نشان دادن راه دیگری، مشکل ما را اصلاح می کنیم. پیدا کردن سه عدد ( u ، v ، w ) به طوری که:

${\ displaystyle {\ begin {cases} x = 1 + 2uØ \\ x = 2 + 3vØ \\ x = 6 + 7w. \\ end {cases}}}$

با قرار دادن x از معادله اول به دوم، ما دریافت می کنیم $1 + 2u \ equiv 2 {\ pmod 3}$ سپس $2u \ equiv 1 {\ pmod 3}$ پس $4u \ equiv 2 \ pmod 3$ پس $u \ equiv 2 \ pmod 3$ یا $ØªÙ = 2 + 3s$ سپس جایگزین x از معادله اول به سوم، با در نظر گرفتن عبارت خواهد شد $1 + 2 (2 + 3s) \ equiv 6 {\ pmod 7}$ پس $s \ equiv 6 \ pmod 7$ پس $x = 1 + 2 (2 + 3 \ cdot 6) = 41$

ادامه نوشته

+ نوشته شده در جمعه دوم آذر ۱۳۹۷ ساعت 12:46 توسط علی رضا نقش نیلچی |

تابع موبیوس

برای هر عدد صحیح مثبت

$n$ ، $μ (n)$

$را$ به عنوان مجموع $n$ ریشه های اولیه $n$ وحدت تعریف می کنیم . این مقدار در { -1 ، 0 ، 1 } به ترتیب با تقسیم کردن $n$ به عوامل اصلی ارزش دارد :

$μ (n) = 1$ اگر $n$ یکعدد صحیح مثبت بدون مربع باتعداد حقیقی از عوامل اولیه باشد.
$μ (n) = -1$ اگر $n$ یک عدد صحیح مثبت بدون مربع با تعداد عددی از عوامل اول باشد.
$μ (n) = 0$ اگر $n$ دارای یک عامل اولیه مربع باشد.

+ نوشته شده در جمعه دوم آذر ۱۳۹۷ ساعت 1:9 توسط علی رضا نقش نیلچی |

آموزش ریاضی

روش Runge-Kutta

دینامیک روش Runge-Kutta

تشخیص یک روش Runge-Kutta S-Stage

ریچاردسون استخراج

آزمایشات عددی

روش Runge-Kutta

روش های روشنی Runge-Kutta

خطا روش عددی

اولری جلوبر

روش هون

روش متمایز صریح

Euler اویلر

رانگ−کوتای

روش های آدامز-بولتون

قضیه باقی مانده چینی 3

مثال از قضیه چینی2

تغییرات و تعمیم ها قضیه چینی

الگوریتم گارنر برای قضیه چینی

الگوریتم بر اساس قضیه چینی بر روی باقی مانده :

الگوریتم بر اساس قضیه چینی بر روی باقی مانده :

مثال از قضیه چینی

تابع موبیوس

تابع فی اویلر

اعداد اول فرما

مثال تابع فی اویلر

فرمول زتا

پیوندهای روزانه

نوشته‌های پیشین

آرشیو موضوعی

پیوندها

آمارگیر وبلاگ

کد پربازدیدترین