Scientific Computing

In a random walk on a two-dimensional grid of points, successive
steps are randomly chosen in the north, south, east, and west
directions with uniform distribution. This module illustrates how such
random walks can be used to approximate the solution to
Laplace's equation,
*u*_{xx} + *u*_{yy} =
0,

The user selects the spacing of the square grid by choosing the
number of interior grid points along each dimension. Next the user
selects the boundary conditions by defining the solution value at each
of the corners of the unit square. The boundary conditions are then
given by linear interpolation of the values at the corners. For
*u*(0, 0) = *a**u*(1, 0) =
*b**u*(0, 1) = *c**u*(1, 1) = *d**u*(*x*, *y*)*a* + *d*
− *b* − *c*) *x* *y**b* − *a*) *x**c*
− *a*) *y**a*

Interior grid points are displayed as small gray dots. By clicking
one of these dots, the user chooses a grid point at which to calculate
the numerical solution. This point, displayed as a slightly larger
black dot, will be the starting point for the random walks. Next the
user clicks *Random Walk*. The resulting random walk is displayed
as a series of line segments moving around the grid until a boundary is
reached, at which point the entire path taken by the random walk is
shown, and the approximate solution value is updated to incorporate
into the average the boundary value at the end of the walk. The exact
solution value, calculated from the equation above, is displayed for
comparison.

To reduce the time needed to obtain a reasonably accurate approximate solution value, the user can choose to take ten random walks at a time. In this mode, the random walks are calculated behind the scenes, and the module displays only a summary of the entire path for each random walk.

Boundary grid points are displayed throughout as colored dots. The color of the boundary point shows how many random walks have ended at that point thus far. The scale below the graph indicates the number of walks corresponding to the color of a boundary point. The color scale changes dynamically as the maximum number of walks ending at a boundary point increases.

**Reference:** Michael T. Heath, *Scientific Computing,
An Introductory Survey*, 2nd edition, McGraw-Hill, New York,
2002. See Computer Problem 13.14 on page 521.

**Developers:** Evan VanderZee and Michael Heath