A web application that could find the real or complex roots of any equation with a single unknown using numerical analysis based on muller method which is an enhanced form of the secant method
Muller's method is a root-finding algorithm, a numerical method for solving equations of the form f(x) = 0. It was first presented by David E. Muller in 1956.Muller's method is based on the secant method, which constructs at every iteration a line through two points on the graph of f. Instead, Muller's method uses three points, constructs the parabola through these three points, and takes the intersection of the x-axis with the parabola to be the next approximation.
The order of convergence of Muller's method is approximately 1.84. This can be compared with 1.62 for the secant method and 2 for Newton's method. So, the secant method makes less progress per iteration than Muller's method and Newton's method makes more progress.
- converges faster than secant method and less than newton method.
- no need to know the derivative.
- applicability to complex valued functions as well. due to the presence of root(b^2 − 4ac).
- 3 initial points are needed (x0, x1, x2).
- F(x0), F(x1), F(x2) must be different else the algorithm fails.
- if F(x0), F(x1), F(x2) are on the same line the secant method will converge faster and easier.
problem : find a root for the equation F(x) given 3 initial points x0, x1, x2 with relative error tolerance ε and with maximimum of N iterations, then plot the function f(x), for each iteration you must find the relative error by using the formula ((x3 - x2)/x3) * 100%
-
inputs :
- f(x)
- x0
- x1
- x2
- ε
- N
-
output :
- list of iterations containing :
- x0
- x1
- x2
- F(p0)
- F(p1)
- F(p2)
- h0
- h1
- Ϭ0
- Ϭ1
- a
- b
- c
- x3
- F(p3)
- ε
- solution
- plot of the function
- list of iterations containing :
-
steps
- Start
- Define list of iterations
- Define n <- 0, h0, h1, f0, f1, f2, Ϭ0, Ϭ1, a, b, c x3, f3, ε
- Read values of F(x), x0, x1, x2, error, N
- h0 <- x1 - x0
- h1 <- x2 - x1
- f0 <- F(x0)
- f1 <- F(x1)
- f2 <- F(x2)
- Ϭ0 <- (f1 - f0)/h0
- Ϭ1 <- (f2 - f1)/h1
- a <- (Ϭ1 - Ϭ0) / (h1 + h0)
- b <- a * h1 + Ϭ1
- c <- fp2
- x3 <- -2c / (b + sign(b)*root(b^2 - 4ac))
- f3 <- F(x3)
- ε <- ((x3 - x2)/x3) * 100%
- n = n + 1
- add x0,x1,x2,f0,f1,f2, Ϭ0, Ϭ1, a, b, c, x3, f3, ε, n as a dictionary to the list iterations
- if n > N or ε <= error
- return to step iv
- return list of iterations
- plot F(x)
- Python: for backend and API design
- HTML (Hyper text markup language): for GUI design
- Css (Cascading style sheets): for GUI design
- java script: for making GUI dynamic and connecting the GUI with the backend
- Django
- bootstrap
- js libraries: for plotting the function graph
- math.js
- plotly.js
- Jquery
- AJAX
Django is a Python-based free and open-source web framework that follows the model–template–views (MTV) architectural pattern. It is maintained by the Django Software Foundation (DSF), an independent organization established in the US as a 501(c)(3) non-profit.
Bootstrap is a free and open-source CSS framework directed at responsive, mobile-first front-end web development. It contains CSS and (optionally) JavaScript-based design templates for typography, forms, buttons, navigation, and other interface component
jQuery is a JavaScript library designed to simplify HTML DOM tree traversal and manipulation, as well as event handling, CSS animation, and Ajax. It is free, open-source software using the permissive MIT License. As of May 2019, jQuery is used by 73% of the 10 million most popular websites. Web analysis indicates that it is the most widely deployed JavaScript library by a large margin, having at least 3 to 4 times more usage than any other JavaScript library.
Math.js is an extensive math library for JavaScript and Node.js. It features a flexible expression parser with support for symbolic computation, comes with a large set of built-in functions and constants, and offers an integrated solution to work with different data types like numbers, big numbers, complex numbers, fractions, units, and matrices. Powerful and easy to use.
Built on top of d3.js and stack.gl, Plotly.js is a high-level, declarative charting library. plotly.js ships with over 40 chart types, including 3D charts, statistical graphs, and SVG maps.
Ajax (short for "Asynchronous JavaScript and XML") is a set of web development techniques that uses various web technologies on the client-side to create asynchronous web applications. With Ajax, web applications can send and retrieve data from a server asynchronously (in the background) without interfering with the display and behaviour of the existing page. By decoupling the data interchange layer from the presentation layer, Ajax allows web pages and, by extension, web applications, to change content dynamically without the need to reload the entire page. In practice, modern implementations commonly utilize JSON instead of XML.
Since our software is a web application powered by django framework, it uses the MTV(Model, Template, View) architecture
when the user enters the url of the software in his browser, an HTTP get request is sent to the server hosting the application where the url is analyzed and routed to the correct view which renders the template and returns it to the client brwoser as an HTTP response which is rendered by the client browser HTTP renderer and dispalyed in the browser window.
After the user enters the data and clicks submission an Ajax request is sent to the server which will read the inputs, find the roots and renders the steps and draws the function as html and returns them as HTTP response which is then rendered by the browser without reloading the page nd the function is plotted using math.js and plotly.js.
- python is better for solving the equation in the backend as its very dynamic and supports complex arthimatic using its cmath module, please refer to Cmath module documentation for more info https://docs.python.org/3/library/cmath.html.
- java script is better for plotting because it runs on the user front end and great in dynamic graphic design which will make the process of drawing use the client personal hardware not the main server resources which will make the service run much faster and more efficient.
the above example works fine for end users who just want to solve an equation, but what about other developers or enterprises that would like to use our software as a service which can be easily integrated with their softwares and systems. thats why we made a REST api for our application
An application programming interface (API) is a connection between computers or between computer programs. It is a type of software interface, offering a service to other pieces of software.A document or standard that describes how to build or use such a connection or interface is called an API specification. A computer system that meets this standard is said to implement or expose an API. The term API may refer either to the specification or to the implementation.
REST has been employed throughout the software industry and is a widely accepted set of guidelines for creating stateless, reliable web APIs. A web API that obeys the REST constraints is informally described as RESTful. RESTful web APIs are typically loosely based on HTTP methods to access resources via URL-encoded parameters and the use of JSON or XML to transmit data
all you need to do as devloper is sending an HTTP request to the server with the following format
http://<application url>/api/muller_method/<equation>/<x0>/<x1>/<x2>/<error margin>/<maximium number of iterations>?format=<format you want to receive in>example: if you enter in your browser http://muller-calculator.herokuapp.com/api/muller_method/x%5E2-cos(x)/1/2/3/0.001/5?format=xml your will have the following result
curl http://muller-calculator.herokuapp.com/api/muller_method/x%5E2-cos(x)/1/2/3/0.001/5?format=xml
submitting a pre-final project for the numerical method project in AASTMT university college of engineering department of computer engineering
https://muller-calculator.herokuapp.com/
- Mohamed Bassel
- Moustafa mohamed wahdan
- Toqa Mohamed Hosni
- Ahmed Tarek Soliman
- Nour Hossam
- Mohamed Hisham El Kafrawy
- muller method theory : http://kilyos.ee.bilkent.edu.tr/~microwave/programs/utilities/numeric1/infoMuller.htm
- math.js library documentation : https://mathjs.org/
- ploly.js library documnetation : https://plotly.com/javascript/
- django frmework : https://www.djangoproject.com/
- cmath python module : https://docs.python.org/3/library/cmath.html
- Ajax : https://developer.mozilla.org/en-US/docs/Web/Guide/AJAX/Getting_Started