Physics 212, 2019: Lecture 2 - Revision history

Ilya: /* How to build a computational model? */

2019-02-03T18:40:15Z

‎How to build a computational model?

Ilya at 18:39, 3 February 2019

2019-02-03T18:39:07Z

Ilya at 18:12, 3 February 2019

2019-02-03T18:12:18Z

Ilya at 18:11, 3 February 2019

2019-02-03T18:11:55Z

Ilya: /* An example of a model: Solving for an equilibrium position, harder version */

2019-01-30T14:13:00Z

‎An example of a model: Solving for an equilibrium position, harder version

Ilya: /* An example of a model: Solving for an equilibrium position, harder version */

2019-01-30T13:22:08Z

‎An example of a model: Solving for an equilibrium position, harder version

Ilya: /* An example of a model: Solving for an equilibrium position, harder version */

2019-01-30T13:19:36Z

‎An example of a model: Solving for an equilibrium position, harder version

Ilya: /* An example of a model: Solving for an equilibrium position, harder version */

2019-01-28T22:18:56Z

‎An example of a model: Solving for an equilibrium position, harder version

Ilya: /* An example of a model: Solving for an equilibrium position, harder version */

2019-01-28T22:18:37Z

‎An example of a model: Solving for an equilibrium position, harder version

Ilya: /* An example of a model: Solving for an equilibrium position, harder version */

2019-01-28T22:12:30Z

‎An example of a model: Solving for an equilibrium position, harder version

@@ Line 68: / Line 68: @@
 Model building proceeds by first identifying the things we know, and the things we need to find out, and listing them clearly. This includes accounting for dimensions of the variables, and for their type: deterministic or not, continuous or not, dynamic or not. From that point, the model building proceeds hierarchically. We first define a few large scale steps that will be needed to get the solution from the known variables. Usually these include the initialization step, a few large-scale computational steps, and then the termination/results output step. Then we move to the computational steps and, for each of them, we break it up into smaller pieces. We continue to break each piece into even smaller pieces until we realize that we already have an implementation for the pieces that we just constructed. In class, we considered the "shut the door!" program as a prototype for a computational model. Opening the door had to be broken down into finding the door, navigating to it, and then shutting it. Then finding the door had to be broken down into scanning the room, comparing snapshots with various door templates, and identifying if any of the snapshots includes an open door. In its turn, comparing to the templates meant loading the set of templates, and so on. Eventually, we come down to a a set of such atomic instructions, where an atom is either understood by the computer directly, or has already been coded by someone else, and can be reused. At this point, the hierarchical construction stops, and we start moving back on the hierarchy towards larger blocks are assembling both initialization and termination steps together: what are the pieces that are needed for each level of the hierarchy to work? And what are the pieces that each level of the hierarchy will output?
-We have spent a lot of time on this in class, and also the ''Python Student's Guide'' has some relevant discussion in the ``Algorithmic Thinking'' section, Chapter 1.
+We have spent a lot of time on this in class, and also the "Python Student's Guide" has some relevant discussion in the "Algorithmic Thinking" section, Chapter 1.
-A key concept that is illustrated by this approach to building computational models is code / model reuse. ''Do not develop models from scratch!'' Your time is valuable
+A key concept that is illustrated by this approach to building computational models is code / model reuse. ''Do not develop models from scratch!'' Your time is valuable. Use the code that either you or somebody else wrote previously, even if this is not the most elegant solution, unless there's an educational value in writing the code on your own.

← Older revision		Revision as of 18:39, 3 February 2019
Line 64:		Line 64:

	Which specific models to use depends on the type of problem you study, and the choice, the explanation of it, and the assumptions involved, should figure prominently in the model-building process.		Which specific models to use depends on the type of problem you study, and the choice, the explanation of it, and the assumptions involved, should figure prominently in the model-building process.
		+
		+	==How to build a computational model?==
		+	Model building proceeds by first identifying the things we know, and the things we need to find out, and listing them clearly. This includes accounting for dimensions of the variables, and for their type: deterministic or not, continuous or not, dynamic or not. From that point, the model building proceeds hierarchically. We first define a few large scale steps that will be needed to get the solution from the known variables. Usually these include the initialization step, a few large-scale computational steps, and then the termination/results output step. Then we move to the computational steps and, for each of them, we break it up into smaller pieces. We continue to break each piece into even smaller pieces until we realize that we already have an implementation for the pieces that we just constructed. In class, we considered the "shut the door!" program as a prototype for a computational model. Opening the door had to be broken down into finding the door, navigating to it, and then shutting it. Then finding the door had to be broken down into scanning the room, comparing snapshots with various door templates, and identifying if any of the snapshots includes an open door. In its turn, comparing to the templates meant loading the set of templates, and so on. Eventually, we come down to a a set of such atomic instructions, where an atom is either understood by the computer directly, or has already been coded by someone else, and can be reused. At this point, the hierarchical construction stops, and we start moving back on the hierarchy towards larger blocks are assembling both initialization and termination steps together: what are the pieces that are needed for each level of the hierarchy to work? And what are the pieces that each level of the hierarchy will output?
		+
		+	We have spent a lot of time on this in class, and also the ''Python Student's Guide'' has some relevant discussion in the ``Algorithmic Thinking'' section, Chapter 1.
		+
		+	A key concept that is illustrated by this approach to building computational models is code / model reuse. ''Do not develop models from scratch!'' Your time is valuable

← Older revision		Revision as of 18:12, 3 February 2019
Line 64:		Line 64:

	Which specific models to use depends on the type of problem you study, and the choice, the explanation of it, and the assumptions involved, should figure prominently in the model-building process.		Which specific models to use depends on the type of problem you study, and the choice, the explanation of it, and the assumptions involved, should figure prominently in the model-building process.
−
−	~~==An example of a model: Solving for an equilibrium position, light version==~~
−	~~A charged particle free to move on a rod is put in the between two particles with an electric charge of the same sign affixed to the end of the rod. Where will the charge come to rest?~~
−
−	;Analysis: How should we model this? is the model dynamic or static? At the first sign, this is a dynamic model, since we are talking about ''motion'' of a charge. On the other hand, we are asked only about the final equilibrium position. Then maybe this is a static model after all -- we only need to know where the charge comes to rest. The model is definitely a continuous space model -- position of the particle is a continuous variable. The model is also deterministic -- there's not a stochastic element present. To make this a static model (so that there's a final rustic point for the charge), there has to be friction, so that the particle does not keep oscillating infinitely. Nothing is mentioned about this in the problem formulation -- but it seems like this is presumed.Does it even make sense that the particle will come to a rest? Same sign particles repel. And the repulsion is stronger when they come closer. So a particle between two other fixed one will be pushed away from both ends -- it seems reasonable that it will come to a steady point at some time if friction robs it of energy.
−
−	;Model building: The equilibrium for the system will be <math>\sum \vec{F}=0</math>. Since the particle is moving on a rod -- in one dimension -- this is equivalent to <math>\sum {F}=0</math>. There are two Coulomb forces acting on the particle from the two end charges. Let's say the charges are at positions <math>x_1</math> and <math>x_2</math>, and have charges <math>q_1</math> and <math>q_2</math>respectively. Let's suppose <math>x_1<x<x_2</math>, where <math>x</math> is the position of the moving charge. The forces acting on the moving charge, which we call <math>q</math> are then <math>\sum F= \frac{qq_1}{(x-p_1)^2}-\frac{qq_2}{(x-p_2)^2}</math>. Thus to solve the problem, we need to solve the following equation for <math>x</math>: <math>\frac{qq_1}{(x-p_1)^2}-\frac{qq_2}{(x-p_2)^2}=0</math>, or, cancelling <math>q</math>, <math>\frac{q_1}{(x-p_1)^2}-\frac{q_2}{(x-p_2)^2}=0</math>. Interestingly, the only variables we need for initialization are the three charge values, and the two end charge positions -- the initial position of the moving charge, and charge value itself seem to be not needed. Multiplying the equation by the two denominators (which, luckily, cannot be zero), we get: <math>{q_1}{(x-p_2)^2}-{q_2}{(x-p_1)^2}=0</math>. Simplifying the equation, we get: <math>(q_1-q_2) x^2 +2(-q_1p_2+q_2p_1)x+(q_1p_2^2-q_2p_1^2)=0 </math>. So it seems that solving this problem is equivalent to solving a simple quadratic equation.
−
−	;Model implementation: To build a model, we start with large blocks describing chunks of the solution of the problem. We progressively break them apart into smaller and smaller blocks, until we are able to write the code for each one of the blocks. At the same time, as we are implementing the blocks, we collect pieces that need to be initialized in the initialization block, and need to be reported in the termination block. Here we realize that, in the previous class hour, we wrote a simple program that solves the quadratic equation <math>ax^2+bx+c=0</math>. Thus implementing the model is equivalent to taking the previously written solution for the quadratic. Thus the implementation will consist of just three blocks: (1) initialization, where we assign <math>a=q_1-q_2</math>, <math>b=2(-q_1p_2+p_2x_1)</math>, and <math>q_1p_2^2+q2p_1^2</math>; (2) solving the quadratic equation and getting its two solutions; and (3) termination, where, of the two solutions, we then output the one that falls between <math>p_1</math> and <math>p_2</math>.
−
−	;Model verification: To verify that the solution is correct, we should try it in cases where the solution is easy to guess or to estimate otherwise, and compare. For example, we can try <math>q_1=q_2</math>, where it's clear that the solution should be <math>x=(p_1+p_2)/2</math>. We could also choose a few conditions with different <math>q_1</math>, and we would expect that growing <math>q_1</math> should push the equilibrium farther from the left end.
−
−	;Discussion: Having solved the problem, we would usually discuss our findings here, and reiterate various constraints and assumptions that entered the solution. However, this problem is too simple too write much here.
−
−	;Your work: Implement the code for solving this problem, using your previous solution of the quadratic equation. Think about various exceptions that can happen with the solution. '''Make sure to submit your code.'''
−
−	~~==An example of a model: Solving for an equilibrium position, harder version==~~
−	A charged particle free to move on a rod is put in the between the first and the second of three immovable particles with an electric charge of the same sign affixed to the rod at various points. Where will the charge come to rest?
−
−	;Analysis: The same analysis as in the simpler version applies here: it's a static, deterministic, continuous space model. We again need the friction for the solution to exist, and the moving particle with come to rest, and the solution will exist.
−
−	;Model building: As before, the equilibrium for the system will be given by <math>\sum {F}=0</math>. There are now three Coulomb forces acting on the particle from the fixed charges. Let's say the charges are at positions <math>p_1<x_2<p_3</math>, with charges <math>q_1</math>, <math>q_2</math>, and <math>q_3</math>, respectively. Let's suppose again that the position of the movable particle is <math>x_1<x<x_2</math>. Then the solution of the problem will be given by <math>\frac{q_1}{(x-p_1)^2}-\frac{q_2}{(x-p_2)^2}-\frac{q_3}{(x-p_3)^2}=0</math>. We notice again that the three charges and fixed charge positions are the only things that are needed for the solution. This is equivalent to <math>{q_1}{(x-p_2)^2}(x-x_3)^2-{q_2}{(x-p_1)^2}(x-p_3)^2 -{q_2}{(x-p_2)^2}(x-p_1)^2=0</math>. This is not a quartic equation in <math>x</math>, and solving this problem would be equivalent to finding the root of this quartic equation between <math>p_1</math> and <math>p_2</math>. This is going to be more interesting!
−
−	;Model implementation: We need to find roots of a fourth order polynomial. How do we do this? For this we will introduce the Newton-Raphson method for finding a root of an equation <math>F(x)=0</math>. Let's suppose that we have a guess <math>x_0</math> for a root. We evaluate the function, <math>F_0=F(x_0)</math>, and it turns out that the guess is not quite right, <math>F_0\neq 0</math>. We can then write the Taylor expansion for the function <math>F</math> for the values of <math>x</math> around <math>x_0</math>. Namely, <math>F(x)\approx F_0 + G_0(x-x_0)</math>, where <math>G_0</math> is the value of the derivative of <math>F</math> evaluated at <math>x_0</math>, <math>G_0=\left(dF/dx\right)_{x_0}</math>. But then we can get a better estimate of where the root is by solving the equation <math> F_0+G_0(x-x_0)=0</math>. This would give <math>x_1=x_0-F_0/G_0</math> for the next estimate. Iterating this, one will get <math>x_{i+1}=x_i -F_i/G_i</math>. This way we will approach the solution progressively better and better, as we iterate more. At some point we will need to stop the iteration. Usually, this is yet another parameter that one adds to the initialization in the experiment: the tolerance <math>\epsilon</math> for finding the solution. That is, one interrupts the recursion when <math>\left\|x_{i+1}-x_i\right\|<\epsilon</math>. Note that the algorithm will only find a root if it is initialized with the initial guess in its vicinity. So if one wants to find a root, one needs to have good guesses. And to find all roots, one needs to have initial guesses near all of the roots. Even then the solution may not exist -- there is no guarantee that the the iterations converge; they can enter cycles or diverge instead. '''Your work:''' with the provided code implementing the Newton-Raphson method, try to find '''all''' roots of the following functions <math>F(x)= {\rm atan} 3x</math> and <math>F(x)=\frac{1}{3+x^2}-\frac{1}{6}</math>. Do you need to modify the code to deal with convergence of the iterations for some conditions? Can you understand why some of your attempts converged to a solution, and some did not? '''Don't forget to submit your code.'''
−
−	~~''More to be added.''~~
−
−	~~;Model verification:~~
−	~~;Discussion:~~

@@ Line 1: / Line 1: @@
 {{PHYS212-2019}}
-In this lecture, we discuss the basics of the modeling process, focusing on simple linear (exponential) bacterial growth as an example.
+In this lecture, we discuss the basics of the modeling process, focusing on a simple static model of finding an equilibrium configuration of charges.
 ==What is a model?==

@@ Line 88: / Line 88: @@
 ;Model implementation: We need to find roots of a fourth order polynomial. How do we do this? For this we will introduce the Newton-Raphson method for finding a root of an equation <math>F(x)=0</math>. Let's suppose that we have a guess <math>x_0</math> for a root. We evaluate the function, <math>F_0=F(x_0)</math>, and it turns out that the guess is not quite right, <math>F_0\neq 0</math>. We can then write the Taylor expansion for the function <math>F</math> for the values of <math>x</math> around <math>x_0</math>. Namely, <math>F(x)\approx F_0 + G_0(x-x_0)</math>, where <math>G_0</math> is the value of the derivative of <math>F</math> evaluated at <math>x_0</math>, <math>G_0=\left(dF/dx\right)_{x_0}</math>. But then we can get a better estimate of where the root is by solving the equation <math> F_0+G_0(x-x_0)=0</math>. This would give <math>x_1=x_0-F_0/G_0</math> for the next estimate. Iterating this, one will get <math>x_{i+1}=x_i -F_i/G_i</math>. This way we will approach the solution progressively better and better, as we iterate more. At some point we will need to stop the iteration. Usually, this is yet another parameter that one adds to the initialization in the experiment: the tolerance <math>\epsilon</math> for finding the solution. That is, one interrupts the recursion when <math>\left|x_{i+1}-x_i\right|<\epsilon</math>. Note that the algorithm will only find a root if it is initialized with the initial guess in its vicinity. So if one wants to find a root, one needs to have good guesses. And to find all roots, one needs to have initial guesses near all of the roots. Even then the solution may not exist -- there is no guarantee that the the iterations converge; they can enter cycles or diverge instead. '''Your work:''' with the provided code implementing the Newton-Raphson method, try to find '''all''' roots of the following functions <math>F(x)= {\rm atan} 3x</math> and <math>F(x)=\frac{1}{3+x^2}-\frac{1}{6}</math>. Do you need to modify the code to deal with convergence of the iterations for some conditions? Can you understand why some of your attempts converged to a solution, and some did not? '''Don't forget to submit your code.'''
 ;Model verification:
 ;Discussion:

@@ Line 85: / Line 85: @@
 ;Analysis: The same analysis as in the simpler version applies here: it's a static, deterministic, continuous space model. We again need the friction for the solution to exist, and the moving particle with come to rest, and the solution will exist.
-;Model building: As before, the equilibrium for the system will be given by <math>\sum {F}=0</math>. There are now three Coulomb forces acting on the particle from the fixed charges. Let's say the charges are at positions <math>x_1<x_2<x_3</math>, with charges <math>q_1</math>, <math>q_2</math>, and <math>q_3</math>, respectively. Let's suppose again that the position of the movable particle is <math>x_1<x<x_2</math>. Then the solution of the problem will be given by <math>\frac{q_1}{(x-x_1)^2}-\frac{q_2}{(x-x_2)^2}-\frac{q_3}{(x-x_3)^2}=0</math>. We notice again that the three charges and fixed charge positions are the only things that are needed for the solution. This is equivalent to <math>{q_1}{(x-x_2)^2}(x-x_3)^2-{q_2}{(x-x_1)^2}(x-x_3)^2 -{q_2}{(x-x_2)^2}(x-x_1)^2=0</math>. This is not a quartic equation in <math>x</math>, and solving this problem would be equivalent to finding the root of this quartic equation between <math>x_1</math> and <math>x_2</math>. This is going to be more interesting!
+;Model building: As before, the equilibrium for the system will be given by <math>\sum {F}=0</math>. There are now three Coulomb forces acting on the particle from the fixed charges. Let's say the charges are at positions <math>p_1<x_2<p_3</math>, with charges <math>q_1</math>, <math>q_2</math>, and <math>q_3</math>, respectively. Let's suppose again that the position of the movable particle is <math>x_1<x<x_2</math>. Then the solution of the problem will be given by <math>\frac{q_1}{(x-p_1)^2}-\frac{q_2}{(x-p_2)^2}-\frac{q_3}{(x-p_3)^2}=0</math>. We notice again that the three charges and fixed charge positions are the only things that are needed for the solution. This is equivalent to <math>{q_1}{(x-p_2)^2}(x-x_3)^2-{q_2}{(x-p_1)^2}(x-p_3)^2 -{q_2}{(x-p_2)^2}(x-p_1)^2=0</math>. This is not a quartic equation in <math>x</math>, and solving this problem would be equivalent to finding the root of this quartic equation between <math>p_1</math> and <math>p_2</math>. This is going to be more interesting!
 ;Model implementation: We need to find roots of a fourth order polynomial. How do we do this? For this we will introduce the Newton-Raphson method for finding a root of an equation <math>F(x)=0</math>. Let's suppose that we have a guess <math>x_0</math> for a root. We evaluate the function, <math>F_0=F(x_0)</math>, and it turns out that the guess is not quite right, <math>F_0\neq 0</math>. We can then write the Taylor expansion for the function <math>F</math> for the values of <math>x</math> around <math>x_0</math>. Namely, <math>F(x)\approx F_0 + G_0(x-x_0)</math>, where <math>G_0</math> is the value of the derivative of <math>F</math> evaluated at <math>x_0</math>, <math>G_0=\left(dF/dx\right)_{x_0}</math>. But then we can get a better estimate of where the root is by solving the equation <math> F_0+G_0(x-x_0)=0</math>. This would give <math>x_1=x_0-F_0/G_0</math> for the next estimate. Iterating this, one will get <math>x_{i+1}=x_i -F_i/G_i</math>. This way we will approach the solution progressively better and better, as we iterate more. At some point we will need to stop the iteration. Usually, this is yet another parameter that one adds to the initialization in the experiment: the tolerance <math>\epsilon</math> for finding the solution. That is, one interrupts the recursion when <math>\left|x_{i+1}-x_i\right|<\epsilon</math>. Note that the algorithm will only find a root if it is initialized with the initial guess in its vicinity. So if one wants to find a root, one needs to have good guesses. And to find all roots, one needs to have initial guesses near all of the roots. Even then the solution may not exist -- there is no guarantee that the the iterations converge; they can enter cycles or diverge instead. '''Your work:''' with the provided code implementing the Newton-Raphson method, try to find '''all''' roots of the following functions <math>F(x)= {\rm atan} 3x</math> and <math>F(x)=\frac{1}{3+x^2}-\frac{1}{6}</math>. Do you need to modify the code to deal with convergence of the iterations for some conditions? Can you understand why some of your attempts converged to a solution, and some did not? '''Don't forget to submit your code.'''

← Older revision		Revision as of 13:19, 30 January 2019
Line 88:		Line 88:

	;Model implementation: We need to find roots of a fourth order polynomial. How do we do this? For this we will introduce the Newton-Raphson method for finding a root of an equation <math>F(x)=0</math>. Let's suppose that we have a guess <math>x_0</math> for a root. We evaluate the function, <math>F_0=F(x_0)</math>, and it turns out that the guess is not quite right, <math>F_0\neq 0</math>. We can then write the Taylor expansion for the function <math>F</math> for the values of <math>x</math> around <math>x_0</math>. Namely, <math>F(x)\approx F_0 + G_0(x-x_0)</math>, where <math>G_0</math> is the value of the derivative of <math>F</math> evaluated at <math>x_0</math>, <math>G_0=\left(dF/dx\right)_{x_0}</math>. But then we can get a better estimate of where the root is by solving the equation <math> F_0+G_0(x-x_0)=0</math>. This would give <math>x_1=x_0-F_0/G_0</math> for the next estimate. Iterating this, one will get <math>x_{i+1}=x_i -F_i/G_i</math>. This way we will approach the solution progressively better and better, as we iterate more. At some point we will need to stop the iteration. Usually, this is yet another parameter that one adds to the initialization in the experiment: the tolerance <math>\epsilon</math> for finding the solution. That is, one interrupts the recursion when <math>\left\|x_{i+1}-x_i\right\|<\epsilon</math>. Note that the algorithm will only find a root if it is initialized with the initial guess in its vicinity. So if one wants to find a root, one needs to have good guesses. And to find all roots, one needs to have initial guesses near all of the roots. Even then the solution may not exist -- there is no guarantee that the the iterations converge; they can enter cycles or diverge instead. '''Your work:''' with the provided code implementing the Newton-Raphson method, try to find '''all''' roots of the following functions <math>F(x)= {\rm atan} 3x</math> and <math>F(x)=\frac{1}{3+x^2}-\frac{1}{6}</math>. Do you need to modify the code to deal with convergence of the iterations for some conditions? Can you understand why some of your attempts converged to a solution, and some did not? '''Don't forget to submit your code.'''		;Model implementation: We need to find roots of a fourth order polynomial. How do we do this? For this we will introduce the Newton-Raphson method for finding a root of an equation <math>F(x)=0</math>. Let's suppose that we have a guess <math>x_0</math> for a root. We evaluate the function, <math>F_0=F(x_0)</math>, and it turns out that the guess is not quite right, <math>F_0\neq 0</math>. We can then write the Taylor expansion for the function <math>F</math> for the values of <math>x</math> around <math>x_0</math>. Namely, <math>F(x)\approx F_0 + G_0(x-x_0)</math>, where <math>G_0</math> is the value of the derivative of <math>F</math> evaluated at <math>x_0</math>, <math>G_0=\left(dF/dx\right)_{x_0}</math>. But then we can get a better estimate of where the root is by solving the equation <math> F_0+G_0(x-x_0)=0</math>. This would give <math>x_1=x_0-F_0/G_0</math> for the next estimate. Iterating this, one will get <math>x_{i+1}=x_i -F_i/G_i</math>. This way we will approach the solution progressively better and better, as we iterate more. At some point we will need to stop the iteration. Usually, this is yet another parameter that one adds to the initialization in the experiment: the tolerance <math>\epsilon</math> for finding the solution. That is, one interrupts the recursion when <math>\left\|x_{i+1}-x_i\right\|<\epsilon</math>. Note that the algorithm will only find a root if it is initialized with the initial guess in its vicinity. So if one wants to find a root, one needs to have good guesses. And to find all roots, one needs to have initial guesses near all of the roots. Even then the solution may not exist -- there is no guarantee that the the iterations converge; they can enter cycles or diverge instead. '''Your work:''' with the provided code implementing the Newton-Raphson method, try to find '''all''' roots of the following functions <math>F(x)= {\rm atan} 3x</math> and <math>F(x)=\frac{1}{3+x^2}-\frac{1}{6}</math>. Do you need to modify the code to deal with convergence of the iterations for some conditions? Can you understand why some of your attempts converged to a solution, and some did not? '''Don't forget to submit your code.'''
		+
		+	;Model verification:
		+	;Discussion:

← Older revision		Revision as of 22:18, 28 January 2019
Line 87:		Line 87:
	;Model building: As before, the equilibrium for the system will be given by <math>\sum {F}=0</math>. There are now three Coulomb forces acting on the particle from the fixed charges. Let's say the charges are at positions <math>x_1<x_2<x_3</math>, with charges <math>q_1</math>, <math>q_2</math>, and <math>q_3</math>, respectively. Let's suppose again that the position of the movable particle is <math>x_1<x<x_2</math>. Then the solution of the problem will be given by <math>\frac{q_1}{(x-x_1)^2}-\frac{q_2}{(x-x_2)^2}-\frac{q_3}{(x-x_3)^2}=0</math>. We notice again that the three charges and fixed charge positions are the only things that are needed for the solution. This is equivalent to <math>{q_1}{(x-x_2)^2}(x-x_3)^2-{q_2}{(x-x_1)^2}(x-x_3)^2 -{q_2}{(x-x_2)^2}(x-x_1)^2=0</math>. This is not a quartic equation in <math>x</math>, and solving this problem would be equivalent to finding the root of this quartic equation between <math>x_1</math> and <math>x_2</math>. This is going to be more interesting!		;Model building: As before, the equilibrium for the system will be given by <math>\sum {F}=0</math>. There are now three Coulomb forces acting on the particle from the fixed charges. Let's say the charges are at positions <math>x_1<x_2<x_3</math>, with charges <math>q_1</math>, <math>q_2</math>, and <math>q_3</math>, respectively. Let's suppose again that the position of the movable particle is <math>x_1<x<x_2</math>. Then the solution of the problem will be given by <math>\frac{q_1}{(x-x_1)^2}-\frac{q_2}{(x-x_2)^2}-\frac{q_3}{(x-x_3)^2}=0</math>. We notice again that the three charges and fixed charge positions are the only things that are needed for the solution. This is equivalent to <math>{q_1}{(x-x_2)^2}(x-x_3)^2-{q_2}{(x-x_1)^2}(x-x_3)^2 -{q_2}{(x-x_2)^2}(x-x_1)^2=0</math>. This is not a quartic equation in <math>x</math>, and solving this problem would be equivalent to finding the root of this quartic equation between <math>x_1</math> and <math>x_2</math>. This is going to be more interesting!

−	;Model implementation: We need to find roots of a fourth order polynomial. How do we do this? For this we will introduce the Newton-Raphson method for finding a root of an equation <math>F(x)=0</math>. Let's suppose that we have a guess <math>x_0</math> for a root. We evaluate the function, <math>F_0=F(x_0)</math>, and it turns out that the guess is not quite right, <math>F_0\neq 0</math>. We can then write the Taylor expansion for the function <math>F</math> for the values of <math>x</math> around <math>x_0</math>. Namely, <math>F(x)\approx F_0 + G_0(x-x_0)</math>, where <math>G_0</math> is the value of the derivative of <math>F</math> evaluated at <math>x_0</math>, <math>G_0=\left(dF/dx\right)_{x_0}</math>. But then we can get a better estimate of where the root is by solving the equation <math> F_0+G_0(x-x_0)=0</math>. This would give <math>x_1=x_0-F_0/G_0</math> for the next estimate. Iterating this, one will get <math>x_{i+1}=x_i -F_i/G_i</math>. This way we will approach the solution progressively better and better, as we iterate more. At some point we will need to stop the iteration. Usually, this is yet another parameter that one adds to the initialization in the experiment: the tolerance <math>\epsilon</math> for finding the solution. That is, one interrupts the recursion when <math>\left\|x_{i+1}-x_i\right\|<\epsilon</math>. Note that the algorithm will only find a root if it is initialized with the initial guess in its vicinity. So if one wants to find a root, one needs to have good guesses. And to find all roots, one needs to have initial guesses near all of the roots. Even then the solution may not exist -- there is no guarantee that the the iterations converge; they can enter cycles or diverge instead. '''Your work:''' with the provided code implementing the Newton-Raphson method, try to find '''all''' roots of the following functions <math>F(x)= {\rm atan} 3x</math> and <math>F(x)=\frac{1}{3+x^2}-\frac{1}{6}</math>. Do you need to modify the code to deal with convergence of the iterations for some conditions? Can you understand why some of your attempts converged to a solution, and some did not?	+	;Model implementation: We need to find roots of a fourth order polynomial. How do we do this? For this we will introduce the Newton-Raphson method for finding a root of an equation <math>F(x)=0</math>. Let's suppose that we have a guess <math>x_0</math> for a root. We evaluate the function, <math>F_0=F(x_0)</math>, and it turns out that the guess is not quite right, <math>F_0\neq 0</math>. We can then write the Taylor expansion for the function <math>F</math> for the values of <math>x</math> around <math>x_0</math>. Namely, <math>F(x)\approx F_0 + G_0(x-x_0)</math>, where <math>G_0</math> is the value of the derivative of <math>F</math> evaluated at <math>x_0</math>, <math>G_0=\left(dF/dx\right)_{x_0}</math>. But then we can get a better estimate of where the root is by solving the equation <math> F_0+G_0(x-x_0)=0</math>. This would give <math>x_1=x_0-F_0/G_0</math> for the next estimate. Iterating this, one will get <math>x_{i+1}=x_i -F_i/G_i</math>. This way we will approach the solution progressively better and better, as we iterate more. At some point we will need to stop the iteration. Usually, this is yet another parameter that one adds to the initialization in the experiment: the tolerance <math>\epsilon</math> for finding the solution. That is, one interrupts the recursion when <math>\left\|x_{i+1}-x_i\right\|<\epsilon</math>. Note that the algorithm will only find a root if it is initialized with the initial guess in its vicinity. So if one wants to find a root, one needs to have good guesses. And to find all roots, one needs to have initial guesses near all of the roots. Even then the solution may not exist -- there is no guarantee that the the iterations converge; they can enter cycles or diverge instead. '''Your work:''' with the provided code implementing the Newton-Raphson method, try to find '''all''' roots of the following functions <math>F(x)= {\rm atan} 3x</math> and <math>F(x)=\frac{1}{3+x^2}-\frac{1}{6}</math>. Do you need to modify the code to deal with convergence of the iterations for some conditions? Can you understand why some of your attempts converged to a solution, and some did not? '''Don't forget to submit your code.'''

← Older revision		Revision as of 22:12, 28 January 2019
Line 87:		Line 87:
	;Model building: As before, the equilibrium for the system will be given by <math>\sum {F}=0</math>. There are now three Coulomb forces acting on the particle from the fixed charges. Let's say the charges are at positions <math>x_1<x_2<x_3</math>, with charges <math>q_1</math>, <math>q_2</math>, and <math>q_3</math>, respectively. Let's suppose again that the position of the movable particle is <math>x_1<x<x_2</math>. Then the solution of the problem will be given by <math>\frac{q_1}{(x-x_1)^2}-\frac{q_2}{(x-x_2)^2}-\frac{q_3}{(x-x_3)^2}=0</math>. We notice again that the three charges and fixed charge positions are the only things that are needed for the solution. This is equivalent to <math>{q_1}{(x-x_2)^2}(x-x_3)^2-{q_2}{(x-x_1)^2}(x-x_3)^2 -{q_2}{(x-x_2)^2}(x-x_1)^2=0</math>. This is not a quartic equation in <math>x</math>, and solving this problem would be equivalent to finding the root of this quartic equation between <math>x_1</math> and <math>x_2</math>. This is going to be more interesting!		;Model building: As before, the equilibrium for the system will be given by <math>\sum {F}=0</math>. There are now three Coulomb forces acting on the particle from the fixed charges. Let's say the charges are at positions <math>x_1<x_2<x_3</math>, with charges <math>q_1</math>, <math>q_2</math>, and <math>q_3</math>, respectively. Let's suppose again that the position of the movable particle is <math>x_1<x<x_2</math>. Then the solution of the problem will be given by <math>\frac{q_1}{(x-x_1)^2}-\frac{q_2}{(x-x_2)^2}-\frac{q_3}{(x-x_3)^2}=0</math>. We notice again that the three charges and fixed charge positions are the only things that are needed for the solution. This is equivalent to <math>{q_1}{(x-x_2)^2}(x-x_3)^2-{q_2}{(x-x_1)^2}(x-x_3)^2 -{q_2}{(x-x_2)^2}(x-x_1)^2=0</math>. This is not a quartic equation in <math>x</math>, and solving this problem would be equivalent to finding the root of this quartic equation between <math>x_1</math> and <math>x_2</math>. This is going to be more interesting!

−	;Model implementation: We need to find roots of a fourth order polynomial. How do we do this? For this we will introduce the Newton-Raphson method for finding a root of an equation <math>F(x)=0</math>. Let's suppose that we have a guess <math>x_0</math> for a root. We evaluate the function, <math>F_0=F(x_0)</math>, and it turns out that the guess is not quite right, <math>F_0\neq 0</math>. We can then write the Taylor expansion for the function <math>F</math> for the values of <math>x</math> around <math>x_0</math>. Namely, <math>F(x)\approx F_0 + G_0(x-x_0)</math>, where <math>G_0</math> is the value of the derivative of <math>F</math> evaluated at <math>x_0</math>, <math>G_0=\left(dF/dx\right)_{x_0}</math>. But then we can get a better estimate of where the root is by solving the equation <math> F_0+G_0(x-x_0)=0</math>. This would give <math>x_1=x_0-F_0/G_0</math> for the next estimate. Iterating this, one will get <math>x_{i+1}=x_i -F_i/G_i</math>. This way we will approach the solution progressively better and better, as we iterate more. At some point we will need to stop the iteration. Usually, this is yet another parameter that one adds to the initialization in the experiment: the tolerance <math>\epsilon</math> for finding the solution. That is, one interrupts the recursion when <math>\left\|x_{i+1}-x_i\right\|<\epsilon</math>.	+	;Model implementation: We need to find roots of a fourth order polynomial. How do we do this? For this we will introduce the Newton-Raphson method for finding a root of an equation <math>F(x)=0</math>. Let's suppose that we have a guess <math>x_0</math> for a root. We evaluate the function, <math>F_0=F(x_0)</math>, and it turns out that the guess is not quite right, <math>F_0\neq 0</math>. We can then write the Taylor expansion for the function <math>F</math> for the values of <math>x</math> around <math>x_0</math>. Namely, <math>F(x)\approx F_0 + G_0(x-x_0)</math>, where <math>G_0</math> is the value of the derivative of <math>F</math> evaluated at <math>x_0</math>, <math>G_0=\left(dF/dx\right)_{x_0}</math>. But then we can get a better estimate of where the root is by solving the equation <math> F_0+G_0(x-x_0)=0</math>. This would give <math>x_1=x_0-F_0/G_0</math> for the next estimate. Iterating this, one will get <math>x_{i+1}=x_i -F_i/G_i</math>. This way we will approach the solution progressively better and better, as we iterate more. At some point we will need to stop the iteration. Usually, this is yet another parameter that one adds to the initialization in the experiment: the tolerance <math>\epsilon</math> for finding the solution. That is, one interrupts the recursion when <math>\left\|x_{i+1}-x_i\right\|<\epsilon</math>. Note that the algorithm will only find a root if it is initialized with the initial guess in its vicinity. So if one wants to find a root, one needs to have good guesses. And to find all roots, one needs to have initial guesses near all of the roots. Even then the solution may not exist -- there is no guarantee that the the iterations converge; they can enter cycles or diverge instead. '''Your work:''' with the provided code implementing the Newton-Raphson method, try to find '''all''' roots of the following functions <math>F(x)= \frac{1}{3+x^2}</math>.