New Adaptive Monte Carlo Algorithm and Application to Financial Mathematics

توضیحات

ABSTRACT

In this paper, a new adaptive Monte Carlo algorithm is proposed to solve linear systems. The proposed algorithm converges much faster than the conventional Monte Carlo algorithm. The corresponding properties of the algorithm are discussed. It has simple structure, low cost, desirable speed and accuracy.Theoretical results are established to justify the convergence of the algorithm. To confirm the accuracy and efficiency of the proposed algorithm, it is used to solve large linear systems. From the numerical results, the new adaptive Monte Carlo algorithm achieves exponential convergence. Both (the new and the old) adaptive Monte Carlo algorithms are implemented for parallel solution of large linear systems on parallel machine with MPI as inter node communication. Furthermore, we provide an application of the algorithm to price options, where the Black Scholes formula is converted to linear systems using discretization.

INTRODUCTION

High dimensional linear systems of algebraic equations are arisen from real world problems: e.g. Real-time speech coding, digital signal  processing, communications, stochastic modelling, and many physical problems involving partial differential equations (see for example ) . Therefore the choice of appropriate approach for solving large sparse linear systems of algebraic equations is a problem of unquestionable importance in many scientific and engineering applications. One of the well known stochastic algorithms which is preferable for solving high dimensional linear system of algebraic equations is Monte Carlo method. The idea is that the solution of the linear system is formulated in terms of the mathematical expectation of some random variable. Then the average of independent samples of this random variable is used to estimate the solution of the linear system. Monte Carlo methods have three significant advantages: 1They can approximate individual components of the solution without calculating the whole solution vector.  2For a large sparse linear system of algebraic equations, they are more efficient than direct or iterative numerical methods. 3They are good candidates for parallelization because of the fact that many  independent sample paths are used to estimate the solution.

چکیده

در این مقاله الگوریتم مونت کارلو سازگار جدید برای حل سیستم های خطی پیشنهاد شده است. الگوریتم پیشنهادی بسیار سریعتر از الگوریتم متداول مونت کارلو همگام می شود. خواص متناظر الگوریتم بحث شده است. این ساختار ساده، هزینه کم، سرعت مطلوب و دقت است. نتایج نظری برای توجیه همگرایی الگوریتم ایجاد شده است. برای تایید صحت و کارایی الگوریتم پیشنهادی، برای حل سیستم های خطی بزرگ مورد استفاده قرار می گیرد. از نتایج عددی، الگوریتم جدید تطبیقی مونت کارلو دستیابی به همگرایی نمایشی است. هر دو الگوریتم مونت کارلو سازگار (جدید و قدیمی) برای راه حل موازی سیستم های خطی بزرگ بر روی دستگاه موازی با MPI به عنوان ارتباط بین گره اجرا می شوند. علاوه بر این، ما یک الگوریتم برای گزینه های قیمت ارائه می دهیم، جایی که فرمول Black Scholes به سیستم های خطی با استفاده از تقسیم بندی تبدیل می شود.

مقدمه

سیستم های خطی با ابعاد بزرگ معادلات جبری از مشکلات دنیای واقعی در آمده است: به عنوان مثال برنامه نویسی زمان واقعی، پردازش سیگنال دیجیتال، ارتباطات، مدل سازی تصادفی، و بسیاری از مشکلات فیزیکی شامل معادلات دیفرانسیل با مشتقات جزئی (به عنوان مثال). بنابراین انتخاب رویکرد مناسب برای حل سیستم های خطی بزرگ خطی معادلات جبری یک مسئله غیر قابل انکار در بسیاری از کاربردهای علمی و مهندسی است. یکی از الگوریتمهای تصادفی شناخته شده که برای حل سیستم خطی بعدی از معادلات جبری ترجیح داده می شود، روش مونت کارلو است. ایده این است که راه حل سیستم خطی از لحاظ انتظار ریاضی برخی متغیر تصادفی فرموله شده است. سپس میانگین نمونه های مستقل از این متغیر تصادفی برای برآورد راه حل سیستم خطی استفاده می شود. روش مونت کارلو دارای سه مزیت قابل توجه است: 1 آنها می توانند اجزای جداگانه محلول را بدون محاسبه کل بردار محلول تقریبی مقایسه کنند. 2 برای یک سیستم خطی بزرگ خطی معادلات جبری، آنها از روش های عددی مستقیم یا تکراری بهتر هستند. 3 آنها داوطلبان خوبی برای موازی سازی هستند به این دلیل که بسیاری از مسیرهای نمونه مستقل برای برآورد راه حل استفاده می شوند.

Year: 2013

Publisher : Third Conference on Mathematical Finance and Applications

By : R. Farnoosh  ,M. Aalaei

File Information: English Language/ 12 Page / size: 373 KB

Only site members can download free of charge after registering and adding to the cart

Download tutorial

سال : 1392

ناشر : سومین کنفرانس ریاضیات مالی و کاربردها

کاری از : R فرنوش ,M آلایی

اطلاعات فایل : زبان انگلیسی / 12 صفحه / حجم : KB 373

فقط اعضای سایت پس از ثبت نام و اضافه کردن به سبد خرید می توانند دانلود رایگان کنند.خوشحال می شویم به ما پبیوندید

آموزش دانلود